@[青溪白石](/user/317008) 有些点 RE 应该是线段树数组开小了，应开成 $maxn\times 4$，即改为 ``Node nodes[maxn*4];``
然后是查询时的树链剖分，一开始的写法是这样：
~~~
int querymax(int x, int y){
int ans = -maxn, fx = top[x], fy = top[y];
while(fx != fy){
if(dep[fx] > dep[fy]){
ans = max(ans, sgt.querymax(rnk[fx], rnk[x], 1));
x = pa[fx];
}
else {
ans = max(ans, sgt.querymax(rnk[fy], rnk[y], 1));
y = pa[fy];
}
fx = top[x], fy = top[y];
}
if(dep[x] > dep[y]) swap(x, y);
ans = max(ans, sgt.querymax(rnk[x], rnk[y], 1));
return ans;
}
~~~
当 $x,y$ 不在同一条链上，那么应该是链顶深度更深的点（假设这个为 $y$），先跳到 $y$ 的链顶，然后再走一条轻链走到另外一条重链的链底。也就是 ``y=pa[top[y]]``。
如果按原来那样写的话，就是 $y$ 先走到它的父亲，然后 $x,y$ 一起跳到链顶。而 $x$ 并不需要跳，并且 $y$ 跳的操作在 $y$ 不是链顶的时候等价于 ``y=top[y]``。
改成下面这样就可以 A 了。
```cpp
#include <iostream>
#include <vector>
using namespace std;
const int maxn = 3*1e4+10;
vector<int> G[maxn];
int w[maxn], pa[maxn], son[maxn], siz[maxn], dep[maxn];
int top[maxn], rnk[maxn], dfn[maxn];
#define ls(x) ((x) << 1)
#define rs(x) (((x) << 1) | 1)
struct Node{
int l, r;
int nmax, nsum;
};
struct Seg{
Node nodes[maxn*4];
void build(int l, int r, int u){
nodes[u].l = l;nodes[u].r = r;
if(l == r){
nodes[u].nmax = nodes[u].nsum = w[dfn[l]];
return;
}
int m = (l+r)>>1;
build(l, m, ls(u));
build(m+1, r, rs(u));
nodes[u].nmax = max(nodes[ls(u)].nmax, nodes[rs(u)].nmax);
nodes[u].nsum = nodes[ls(u)].nsum + nodes[rs(u)].nsum;
}
void add(int del, int x, int u){
if(nodes[u].l == nodes[u].r) {
nodes[u].nmax -= del;
nodes[u].nsum -= del;
return;
}
if(nodes[ls(u)].r >= x) add(del, x, ls(u));
else add(del, x, rs(u));
nodes[u].nmax = max(nodes[ls(u)].nmax, nodes[rs(u)].nmax);
nodes[u].nsum = nodes[ls(u)].nsum + nodes[rs(u)].nsum;
}
int querymax(int l, int r, int u){
if(nodes[u].l >= l && nodes[u].r <= r) return nodes[u].nmax;
int ans = -maxn;
if(l <= nodes[ls(u)].r) ans = max(ans, querymax(l, r, ls(u)));
if(r >= nodes[rs(u)].l) ans = max(ans, querymax(l, r, rs(u)));
return ans;
}
int querysum(int l, int r, int u){
if(nodes[u].l >= l && nodes[u].r <= r) return nodes[u].nsum;
int ans = 0;
if(l <= nodes[ls(u)].r) ans += querysum(l, r, ls(u));
if(r >= nodes[rs(u)].l) ans += querysum(l, r, rs(u));
return ans;
}
}sgt;
void pre(int u){
siz[u] = 1;
son[u] = -1;
for(int i = 0; i < G[u].size(); i++){
int v = G[u][i];
if(v == pa[u]) continue;
pa[v] = u;
dep[v] = dep[u]+1;
pre(v);
if(son[u] == -1 || siz[v] > siz[son[u]])son[u] = v;
siz[u] += siz[v];
}
}
int cnt = 0;
void dfs(int u, int tp){
cnt++;
rnk[u] = cnt;
dfn[cnt] = u;
top[u] = tp;
if(son[u] != -1){
dfs(son[u], tp);
}
for(int i = 0; i < G[u].size(); i++){
int v = G[u][i];
if(v == pa[u] || v == son[u]) continue;
dfs(v, v);
}
}
int querymax(int x, int y){
int ans = -maxn;
while(top[x] != top[y]){
if(dep[top[x]] > dep[top[y]]) {
ans = max(ans, sgt.querymax(rnk[top[x]], rnk[x], 1));
x=pa[top[x]];
}
else {
ans = max(ans, sgt.querymax(rnk[top[y]], rnk[y], 1));
y=pa[top[y]];
}
}
if(dep[x] > dep[y]) swap(x, y);
ans = max(ans, sgt.querymax(rnk[x], rnk[y], 1));
return ans;
}
int querysum(int x, int y){
int ans = 0;
while(top[x] != top[y]){
if(dep[top[x]] > dep[top[y]]){
ans += sgt.querysum(rnk[top[x]], rnk[x], 1);
x=pa[top[x]];
}
else {
ans += sgt.querysum(rnk[top[y]], rnk[y], 1);
y=pa[top[y]];
}
}
if(dep[x] > dep[y]) swap(x, y);
ans += sgt.querysum(rnk[x], rnk[y], 1);
return ans;
}
int main(){
int n; cin >> n;
for(int i = 1; i < n; i++){
int a, b; cin >> a >> b;
G[a].push_back(b);
G[b].push_back(a);
}
for(int i = 1; i <= n; i++)
cin >> w[i];
pre(1);
dfs(1, 1);
//for(int i = 1; i <= n; i++) cout << son[i] << " ";
//for(int i = 1; i <= n; i++) cout << dfn[i] << " ";
sgt.build(1, n, 1);
int q; cin >> q;
while(q--){
string s; cin >> s;
if(s == "CHANGE"){
int u, t; cin >> u >> t;
int d = w[u] - t;
w[u] = t;
sgt.add(d, rnk[u], 1);
}
if(s == "QMAX"){
int u, v; cin >> u >> v;
cout << querymax(u, v) << endl;
}
if(s == "QSUM"){
int u, v; cin >> u >> v;
cout << querysum(u, v) << endl;
}
}
//for(int i = 1; i <= n; i++) cout << w[i] << " ";
}
```
by Cloote @ 2024-01-22 15:57:40
@[Cloote](/user/248359) 谢谢！（不过已经关注了hhh）
by 青溪白石 @ 2024-01-22 20:01:08