【MX-S7-T2】「SMOI-R2」Speaker题解
consequence
·
·
题解
【MX-S7-T2】「SMOI-R2」Speaker 题解
先考虑特殊性质 C。
设 1 为根节点。
设 dp_x 表示以 x 为根的子树所能贡献的最大值，对于 x 的一个孩子 s，设它们之间的距离为 d，显然有转移：dp_x = \max dp_s - 2d。
对于一个点对 $(a, b)$，设两点间的路径为 $A$，答案就应当是 $c_a + c_b + \max\limits_{i \in A} dp_i - dis_{a, b}$，树剖后用 ST 表维护路径上最大值即可。
再考虑一般情况。
相较于特殊情况，一般情况的答案还可能是在 $lca_{a, b}$ 到根节点的路径上的某个点的子树上的点演出。
设 $fdp_x$ 表示点 $x$ 在这种情况下的答案的答案，设 $p$ 为 $x$ 的父亲，有转移 $fdp_x = \max(c_x, fdp_p - 2dis_{x, p})$。
$fdp_x$ 的初值为 $dp_x$。
最后答案即为 $c_a + c_b + \max\limits_{i \in A} (dp_i,fdp_{lca_{a, b}}) - dis_{a, b}$。
时间复杂度 $O(n \log n)$。
## 丑陋的赛时 AC 代码：
```cpp
#include <bits/stdc++.h>
#define mp make_pair
#define fr first
#define sc second
using namespace std;
typedef pair<long long, int> pii;
const int MAXN = 2e5 + 10;
vector<pii> v[MAXN];
long long st[MAXN][24 + 5];
long long dp[MAXN], c[MAXN], fdp[MAXN], dis[MAXN];
int f[MAXN], d[MAXN], sz[MAXN], son[MAXN], top[MAXN], id[MAXN];
int n, q, cnt;
long long ask(int l, int r) {
int k = log(r - l + 1) / log(2);
return max(st[l][k], st[r - (1 << k) + 1][k]);
}
long long query(int x, int y) {
long long val = LLONG_MIN;
int fx = x, fy = y;
while (top[x] != top[y]) {
if (d[top[x]] < d[top[y]]) swap(x, y);
val = max(val, ask(id[top[x]], id[x]));
x = f[top[x]];
}
if (d[x] > d[y]) swap(x, y);
val = max(val, ask(id[x], id[y]));
val = max(val, fdp[id[x]]);
return val + 2 * dis[x] - dis[fx] - dis[fy] + c[fx] + c[fy];
}
void dfs1(int x, int p) {
d[x] = d[p] + 1;
f[x] = p;
int maxson = -1;
for (int i = 0; i < v[x].size(); ++i) {
int nx = v[x][i].sc;
if (nx == p) continue;
dis[nx] = dis[x] + v[x][i].fr;
dfs1(nx, x);
sz[x] += sz[nx];
if (sz[nx] > maxson) {
maxson = sz[nx];
son[x] = nx;
}
}
sz[x]++;
}
void dfs2(int x, int ntop) {
id[x] = ++cnt;
top[x] = ntop;
if (!son[x]) return;
dfs2(son[x], ntop);
for (int i = 0; i < v[x].size(); ++i) {
int nx = v[x][i].sc;
if (nx == f[x] || nx == son[x]) continue;
dfs2(nx, nx);
}
}
void dfs3(int x, int p) {
dp[id[x]] = c[x];
for (int i = 0; i < v[x].size(); ++i) {
int nx = v[x][i].sc;
if (nx == p) continue;
dfs3(nx, x);
dp[id[x]] = max(dp[id[x]], dp[id[nx]] - 2 * v[x][i].fr);
}
fdp[id[x]] = dp[id[x]];
}
void dfs4(int x, int p) {
for (int i = 0; i < v[x].size(); ++i) {
int nx = v[x][i].sc;
if (nx == p) {
fdp[id[x]] = max(fdp[id[x]], fdp[id[nx]] - 2 * v[x][i].fr);
break;
}
}
for (int i = 0; i < v[x].size(); ++i) {
int nx = v[x][i].sc;
if (nx == p) continue;
dfs4(nx, x);
}
}
int main() {
cin.tie(0), cout.tie(0), ios::sync_with_stdio(false);
cin >> n >> q;
for (int i = 1; i <= n; ++i) cin >> c[i];
for (int i = 1; i < n; ++i) {
int a, b;
long long nd;
cin >> a >> b >> nd;
v[a].push_back(mp(nd, b));
v[b].push_back(mp(nd, a));
}
dfs1(1, 1);
dfs2(1, 1);
//树链剖分
dfs3(1, 1);//转移dp
dfs4(1, 1);//转移fdp，其实可以在建ST表时直接用fdp
int maxk = log(n) / log(2) + 1;
for (int i = 1; i <= n; ++i) st[i][0] = dp[i];
for (int j = 1; j <= maxk; ++j) {
for (int i = 1; i + (1 << j) <= n + 1; ++i) {
st[i][j] = max(st[i][j - 1], st[i + (1 << (j - 1))][j - 1]);
}
}//ST表
for (int i = 1; i <= q; ++i) {
int a, b;
cin >> a >> b;
cout << query(a, b) << "\n";
}
return 0;
}
```