【-71】3305 水果姐逛水果街Ⅱ[倍增LCA]

题目描述 Description

水果姐第二天心情也很不错,又来逛水果街。突然,cgh又出现了。cgh施展了魔法,水果街变成了树结构(店与店之间只有一条唯一的路径)。同样还是n家水果店,编号为$1$~$n$,每家店能买水果也能卖水果,并且同一家店卖与买的价格一样。cgh给出$m$个问题,每个问题要求水果姐从第$x$家店出发到第y家店,途中只能选一家店买一个水果,然后选一家店 (可以是同一家店,但不能往回走)卖出去。求最多可以赚多少钱。水果姐向学过oi的你求助。

输入描述 Input Description

第一行$n$,表示有n家店下来$n$个正整数,表示每家店一个苹果的价格。下来$n-1$行,每行两个整数$x,y$,表示第$x$家店和第$y$家店有一条边。下来一个整数$m$,表示下来有$m$个询问。下来有$m$行,每行两个整数$x$和$y$,表示从第$x$家店出发到第$y$家店。

输出描述 Output Description

有 $m$ 行。每行对应一个询问,一个整数,表示面对cgh的每次询问,水果姐最多可以赚到多少钱。

样例输入 Sample Input

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
10
16 5 1 15 15 1 8 9 9 15
1 2
1 3
2 4
2 5
2 6
6 7
4 8
1 9
1 10
6
9 1
5 1
1 7
3 3
1 1
3 6

样例输出 Sample Output7

1
2
3
4
5
11
7
0
0
15

数据范围及提示 Data Size & Hint

$0<=苹果的价格<=10^8$

$0<n<=200000$

$0<m<=10000$

题解

这道题简直有毒.

因为不能往回走,所以单纯的维护$max$和$min$ 是不够的.

还需要维护两个$ans$,一个是从这个节点往根节点走的 $ans$,另一个是从根节点往这个节点走的$ans$ .

在更新$ans$的时候,有多种情况

  1. 某一部分的ans
  2. 如果是从 $x->lca(x,y)$ 的 $ans$ , 可以下面部分取 $min$ ,上面部分取$max$进行更新
  3. 如果是从$lca(x,y)->y$ 的 $ans$ ,可以在下面部分取 $max$, 上面部分取 $min$ 进行更新
  4. 然后可以$x->lca(x,y)$ 取 $min$ ,$lca(x,y)->y$ 取 $max$ 进行更新
  5. 然后不要忘记用他们的最近公共祖先更新 $min$ 和 $max$

嗯表述很奇怪,具体看代码,代码还是很好懂的

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
#include<bits/stdc++.h>
using namespace std;
int read()
{
char s;
int k=0,base=1;
while((s=getchar())!='-'&&s!=EOF&&!(s>='0'&&s<='9'));
if(s==EOF)exit(0);
if(s=='-')base=-1,s=getchar();
while(s>='0'&&s<='9')
{
k=k*10+(s-'0');
s=getchar();
}
return k*base;
}
void write(int x)
{
if(x<0)
{
putchar('-');
write(-x);
}
else
{
if(x/10)write(x/10);
putchar(x%10+'0');
}
}
const int maxn=200010;
int n,Q;//点的个数,询问个数
int a[maxn];//点权
int f[30][maxn];//存父亲
int m[30][maxn];//max
int s[30][maxn];//min
int ans1[30][maxn];//往上走到根的ans
int ans2[30][maxn];//从根往下走的ans
int to[maxn*2];//链式前向星
int ne[maxn*2];
int po[maxn];
int de[maxn];
int maxde,Log;//记录最大深度,要搜多少
int lb;
int X,Y;
inline void add(int x,int y)//加边
{
lb++;to[lb]=y;ne[lb]=po[x];po[x]=lb;
}
inline void dfs(int x)
{
maxde=max(maxde,de[x]);//更新最大深度
for (int i=po[x];i;i=ne[i])
{
if (f[0][x]!=to[i])//如果这条边连的不是父亲
{
int xx=to[i];
f[0][xx]=x;//xx的父亲是x
m[0][xx]=max(a[x],a[xx]);//更新max
s[0][xx]=min(a[x],a[xx]);//更新min
ans1[0][xx]=max(0,-a[xx]+a[x]);//更新ans1,往上走就是减去自己的点权+父亲的点权
ans2[0][xx]=max(0,-a[x]+a[xx]);//更新ans2
de[xx]=de[x]+1;//记录深度
dfs(xx);//往下扫
}
}
}
inline int find(int x,int y)//x->y
{
int ans=0;
int Max=a[y];//存终点到lca的max
int Min=2333333;//存起点到lca的min
if (de[x]>de[y])//使2者深度相同,因为起点和终点不能换位置
{//所以判断,分开搞
for (int i=0;i<Log;i++)
{
if ((de[x]-de[y])>>i & 1)//de[x]-de[y]转成二进制后第i位如果为1就要往上移那么多
{
ans=max(ans,ans1[i][x]);
ans=max(ans,-Min+m[i][x]);//更新ans,之后才能更新min(因为min更新之后就包括x~x+2^i那一部分,就会gg)
Min=min(Min,s[i][x]);//更新min
x=f[i][x];//更新x,这个要最后更新
}
}
} else
if (de[x]<de[y])
{
for (int i=0;i<Log;i++)
{
if ((de[y]-de[x])>>i & 1)
{
ans=max(ans,ans2[i][y]);
ans=max(ans,Max-s[i][y]);
Max=max(Max,m[i][y]);//更新Max,同理
y=f[i][y];
}
}
}
for (int i=Log-1;i>=0;i--)
{
if (f[i][x]!=f[i][y]&&f[i][x]!=-1&&f[i][y]!=-1)
{//如果往上跳2^i次方祖先不同就网上跳
ans=max(ans,ans1[i][x]);//更新ans
ans=max(ans,-Min+m[i][x]);//更新ans,然后更新min
Min=min(Min,s[i][x]);//更新min

ans=max(ans,ans2[i][y]);//更新ans
ans=max(ans,Max-s[i][y]);
Max=max(Max,m[i][y]);//更新min
x=f[i][x];//往上跳
y=f[i][y];
}
}//所以我不知道我为何要这个奇怪的特判
if (x!=y&&f[0][x]!=-1) Min=min(Min,s[0][x]);//然后还要更新一次,因为可以在
if (x!=y&&f[0][y]!=-1) Max=max(Max,m[0][y]);//他们lca的地方进行交易
//某些奇怪的判断(什么if(x!=y)是我倍增的bug,我也不知道为什么)
ans=max(ans,Max-Min);
return ans;
}
int main()
{
n=read();
memset(f,-1,sizeof(f));
for (int i=1;i<=n;i++) a[i]=read();//读入点权
for (int i=1;i<n;i++)
{
X=read();Y=read();
add(X,Y);add(Y,X);//加边
}
m[0][1]=a[1];s[0][1]=a[1];de[1]=1;
dfs(1);//预处理
while (maxde)
{
maxde/=2;
Log++;
}
for (int i=1;i<Log;i++)
for (int j=1;j<=n;j++)
{//求点j的2^i祖先
if (j==1) continue;//1为根节点,不需要往上扫了
if (f[i-1][j]==-1) continue;//没有第2^(i-1)个祖先也不用扫了
f[i][j]=f[i-1][f[i-1][j]];
//j的2^i祖先=j的2^(i-1)个祖先的2^(i-1)个祖先
if (f[i][j]==-1) continue;//没有2^i祖先也不用更新了
m[i][j]=max(m[i-1][j],m[i-1][f[i-1][j]]);//更新max
s[i][j]=min(s[i-1][j],s[i-1][f[i-1][j]]);//更新min
ans1[i][j]=max(ans1[i-1][j],ans1[i-1][f[i-1][j]]);//更新ans
ans1[i][j]=max(ans1[i][j],-s[i-1][j]+m[i-1][f[i-1][j]]);
ans2[i][j]=max(ans2[i-1][j],ans2[i-1][f[i-1][j]]);
ans2[i][j]=max(ans2[i][j],m[i-1][j]-s[i-1][f[i-1][j]]);
}
Q=read();
while (Q--)
{
X=read();Y=read();
if (X==Y) //特判掉
{
printf("0\n");
continue;
}
printf("%d\n",find(X,Y));//从x->y,输出
}
return 0;
}