P11324 【MX-S7-T2】「SMOI-R2」Speaker
Rt__
·
·
题解
P11324 【MX-S7-T2】「SMOI-R2」Speaker
题意简述
给一棵树，以及每条边的代价，在点 u 演讲可以获得 c_u 的权值，给定 q 个询问，每次询问给定 x 和 y，求出一天在 x、y 和其他任意一个点 z 上演讲三次所能获得的最大权值
即求：
W = c_x + c_z + c_y + d_{x, z} + d_{z, y}
的值。
思路
然后我们考虑点 $z$。他可以看作 $x->y$ 路径上伸出来的一个枝节（可以向上/下），或者它本身就是在 $x->y$ 路径上的点（例如 $x$ $y$ 的公共祖先）。
所以我们可以把每个点向下延伸出去（或者不延伸）的最大贡献求出来，再次利用一个倍增数组来保存跳一次经过所有的点的最大延伸贡献，在找 LCA 时取 max，就可以找出若向下延伸可以做的最大贡献。
再考虑向上延伸。发现若向上延伸，一定是再 LCA 处。所以我们在 DFS 时，顺便记录向上延伸的最大贡献，就可以和之前取的 max 再取 max 加到答案里就可以。
一定要注意在处理向上延伸的情况时，不只有
还可能是
的情况，一定要考虑周全。
## 代码
```cpp
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define endl '\n'
inline ll read(){
ll res = 0, f = 1;
char c = getchar();
while(c < '0' || c > '9'){
if(c == '-')f = -1;
c = getchar();
}
while(c >= '0' && c <= '9'){
res = res * 10 + c - '0';
c = getchar();
}
return res * f;
}
const int N = 300010;
const ll INF = 0x3f3f3f3f3f3f3f3f;
ll c[N];
ll h[N], ne[N * 2], e[N * 2], w[N * 2], idx;
void add(ll a, ll b, ll c){
e[idx] = b, ne[idx] = h[a], w[idx] = c, h[a] = idx ++;
return;
}
ll f[N][20], max_sp[N], cost[N][20], max_down[N][20], deep[N], max_up[N];
void dfs(ll u, ll fa){
f[u][0] = fa;
deep[u] = deep[fa] + 1;
max_sp[u] = c[u];
for(int i = 1; i <= 17; i ++){
f[u][i] = f[f[u][i - 1]][i - 1];
cost[u][i] = cost[u][i - 1] + cost[f[u][i - 1]][i - 1];
}
for(int i = h[u]; i != -1; i = ne[i]){
int j = e[i];
if(j == fa)continue;
cost[j][0] = w[i];
dfs(j, u);
max_sp[u] = max(max_sp[u], max_sp[j] - 2 * w[i]);
}
return;
}
void dfss(ll u, ll fa, ll maxx){
max_down[u][0] = max(max_sp[u], max_sp[fa]);
for(int i = 1; i <= 17; i ++){
max_down[u][i] = max(max_down[u][i - 1], max_down[f[u][i - 1]][i - 1]);
}
max_up[u] = max(maxx, max_sp[u]);
for(int i = h[u]; i != -1; i = ne[i]){
int j = e[i];
if(j == fa)continue;
dfss(j, u, max_up[u] - 2 * w[i]);
}
return;
}
ll ans(ll u, ll v){
ll res = c[u] + c[v];
ll maxx = max(max_sp[u], max_sp[v]);
if(deep[u] < deep[v])swap(u, v);
for(int i = 17; i >= 0; i --){
if(deep[f[u][i]] >= deep[v]){
res -= cost[u][i];
maxx = max(maxx, max_down[u][i]);
u = f[u][i];
}
}
if(u == v){
maxx = max(maxx, max_up[u]);
maxx = max(maxx, max_sp[u]);
return res + maxx;
}
for(int i =17; i >= 0; i --){
if(f[u][i] != f[v][i]){
res -= cost[u][i];
res -= cost[v][i];
maxx = max(maxx, max_up[u]);
maxx = max(maxx, max_up[v]);
maxx = max(maxx, max_down[u][i]);
maxx = max(maxx, max_down[v][i]);
u = f[u][i];
v = f[v][i];
}
}
res -= cost[u][0];
res -= cost[v][0];
ll LCA = f[u][0];
maxx = max(maxx, max_up[LCA]);
maxx = max(maxx, max_down[u][0]);
maxx = max(maxx, max_down[v][0]);
return res + maxx;
}
signed main(){
memset(h, -1, sizeof h);
ll n = read(), q = read();
for(int i = 1; i <= n; i ++){
c[i] = read();
}
for(int i = 1; i < n; i ++){
ll u = read(), v = read(), W = read();
add(u, v, W), add(v, u, W);
}
dfs(1, 0);
dfss(1, 0, 0);
while(q --){
ll u = read(), v = read();
cout << ans(u, v) << endl;
}
return 0;
}
```