QwQ
其实就是求以x为根的子树到0点的距离最大值。用dfs序把每一个结点对应的子树区间和到0点的距离求出来，挂到线段树上，修改的时候直接在线段树上修改整个区间即可。
（不太详细，待更……）
爆搜代码
#pragma comment(linker, "/STACK:1024000000,1024000000") #include<iostream> #include<cstdio> #include<cstring> using namespace std; const int L = 100005; struct Node { int to , next; }; Node e[2*L]; int T , n , m , val[L] , head[L] , tot , ans , flag; void add(int x , int y) { tot++; e[tot].next = head[x]; e[tot].to = y; head[x] = tot; } int dfs(int u , int f , int aim) { if(u==aim) { flag = f; return 1; } for(int i=head[u]; i; i=e[i].next) { int v = e[i].to; if(v==f) continue; if(dfs(v , u , aim)) { ans += val[v]; return 1; } } return 0; } void dfs2(int u , int f) { for(int i=head[u]; i; i=e[i].next) { int v = e[i].to; if(v==f||val[v]<0) continue; ans += val[v]; dfs2(v , u); } } int main() { scanf("%d",&T); for(int t=1; t<=T; t++) { memset(head , 0 , sizeof(head)); tot = 0; scanf("%d%d",&n,&m); for(int i=1; i<n; i++) { int x , y; scanf("%d%d",&x,&y); add(x , y); add(y , x); } for(int i=0; i<n; i++) scanf("%d",&val[i]); printf("Case #%d:\n",t); for(int i=1; i<=m; i++) { int opt; scanf("%d",&opt); if(opt==0) { int x , y; scanf("%d%d",&x,&y); val[x] = y; } else { int x; scanf("%d",&x); ans = val[0]; dfs(0 , 0 , x); dfs2(x , flag); printf("%d\n",ans); } } } return 0; }正解代码
#pragma comment(linker, "/STACK:1024000000,1024000000") #include<iostream> #include<cstdio> #include<cstring> #define INF 1e18 using namespace std; const long long L = 100005; struct Node { long long to , next; }; Node e[2*L]; struct Seg { long long l , r , sum , lazy; }; Seg tree[4*L]; long long T , n , m , val[L] , head[L] , tot , num , d[L] , l[L] , r[L] , nd[L]; inline long long mymax(long long a , long long b) { return a>b?a:b; } void add(long long x , long long y) { tot++; e[tot].next = head[x]; e[tot].to = y; head[x] = tot; } void dfs(long long u , long long f) { num++; l[u] = num; nd[num] = u; for(int i=head[u]; i; i=e[i].next) { long long v = e[i].to; if(v==f) continue; d[v] = d[u] + val[v]; dfs(v , u); } r[u] = num; } void build(long long num , long long l , long long r) { tree[num].l = l; tree[num].r = r; tree[num].lazy = 0; if(l==r) { tree[num].sum = d[nd[l]]; return ; } long long mid = (l+r)>>1; build(num<<1 , l , mid); build(num<<1|1 , mid+1 , r); tree[num].sum = mymax(tree[num<<1].sum , tree[num<<1|1].sum); } void pushdown(long long num) { if(tree[num].lazy) { tree[num<<1].sum += tree[num].lazy; tree[num<<1|1].sum += tree[num].lazy; tree[num<<1].lazy += tree[num].lazy; tree[num<<1|1].lazy += tree[num].lazy; tree[num].lazy = 0; } } void update(long long num , long long l , long long r , long long add) { if(l<=tree[num].l&&r>=tree[num].r) { tree[num].lazy += add; tree[num].sum += add; return ; } long long mid = (tree[num].l+tree[num].r)>>1; pushdown(num); if(l<=mid) update(num<<1 , l , r , add); if(mid<r) update(num<<1|1 , l , r , add); tree[num].sum = mymax(tree[num<<1].sum , tree[num<<1|1].sum); } long long query(long long num , long long l , long long r) { if(l<=tree[num].l&&r>=tree[num].r) return tree[num].sum; long long mid = (tree[num].l+tree[num].r)>>1; pushdown(num); long long ans = -INF; if(l<=mid) ans = mymax(ans , query(num<<1 , l , r)); if(r>mid) ans = mymax(ans , query(num<<1|1 , l , r)); return ans; } int main() { scanf("%lld",&T); for(int t=1; t<=T; t++) { num = 0; memset(head , 0 , sizeof(head)); tot = 0; scanf("%lld%lld",&n,&m); for(int i=1; i<n; i++) { long long x , y; scanf("%lld%lld",&x,&y); add(x , y); add(y , x); } for(int i=0; i<n; i++) scanf("%lld",&val[i]); d[0] = val[0]; dfs(0 , -1); build(1 , 1 , n); printf("Case #%d:\n",t); for(int i=1; i<=m; i++) { long long opt; scanf("%lld",&opt); if(opt==0) { long long x , y; scanf("%lld%lld",&x,&y); update(1 , l[x] , r[x] , y-val[x]); val[x] = y; } else { long long x; scanf("%lld",&x); printf("%lld\n",query(1 , l[x] , r[x])); } } } return 0; }