Description 一棵有向树，1是根，每个点有点权，两种操作： Q u：查询u节点为根节点的子树中权值最大值与最小值的差 R u x：给以u节点为根节点的子树所有点点权加上x Input 第一行一整数T表示用例组数，每组用例首先输入一整数n表示点数，之后n-1个数，第i个数表示i+1点的父亲节点，之后n个数c[i]表示每个点的点权，然后输入一整数q表示操作数，最后q行每行一种操作 (2<=n<=1e6,1<=m<=1e4,1<=c[i]<=1e3,1<=x<=1e3) Output 对于每次查询操作，输出结果 Sample Input 1 5 1 1 2 2 10 6 8 4 5 7 Q 2 Q 3 R 4 2 Q 2 Q 1 R 2 4 Q 1 Sample Output 2 0 1 5 2 Solution 求出每个点的dfs序后，两种操作分别变成查询区间最大值最小值以及区间更新，线段树即可 Code
#include<cstdio> #include<iostream> #include<cstring> #include<algorithm> #include<cmath> #include<vector> #include<queue> #include<map> #include<set> #include<ctime> using namespace std; #define INF 0x3f3f3f3f #define maxn 1111111 int T,n,q,ll[maxn],rr[maxn],index; vector<int>g[maxn]; void dfs(int u) { ll[u]=++index; for(int i=0;i<g[u].size();i++)dfs(g[u][i]); rr[u]=index; } #define ls (t<<1) #define rs ((t<<1)|1) int Max[maxn<<2],Min[maxn<<2],Plus[maxn<<2]; void build(int l,int r,int t) { Max[t]=Min[t]=Plus[t]=0; if(l==r)return ; int mid=(l+r)>>1; build(l,mid,ls),build(mid+1,r,rs); } void push_up(int t) { Max[t]=max(Max[ls],Max[rs]); Min[t]=min(Min[ls],Min[rs]); } void push_down(int t) { if(Plus[t]) { int tt=Plus[t]; Plus[t]=0; Max[ls]+=tt,Min[ls]+=tt,Plus[ls]+=tt; Max[rs]+=tt,Min[rs]+=tt,Plus[rs]+=tt; } } void update(int L,int R,int l,int r,int t,int v) { if(L<=l&&r<=R) { Min[t]+=v,Max[t]+=v,Plus[t]+=v; return ; } push_down(t); int mid=(l+r)>>1; if(L<=mid)update(L,R,l,mid,ls,v); if(R>mid) update(L,R,mid+1,r,rs,v); push_up(t); } int query_max(int L,int R,int l,int r,int t) { if(L<=l&&r<=R)return Max[t]; push_down(t); int ans=0; int mid=(l+r)>>1; if(L<=mid)ans=max(ans,query_max(L,R,l,mid,ls)); if(R>mid)ans=max(ans,query_max(L,R,mid+1,r,rs)); return ans; } int query_min(int L,int R,int l,int r,int t) { if(L<=l&&r<=R)return Min[t]; push_down(t); int ans=INF; int mid=(l+r)>>1; if(L<=mid)ans=min(ans,query_min(L,R,l,mid,ls)); if(R>mid)ans=min(ans,query_min(L,R,mid+1,r,rs)); return ans; } int main() { scanf("%d",&T); while(T--) { scanf("%d",&n); index=0; for(int i=1;i<=n;i++)g[i].clear(); for(int i=1;i<n;i++) { int fa; scanf("%d",&fa); g[fa].push_back(i+1); } dfs(1); build(1,n,1); for(int i=1;i<=n;i++) { int c; scanf("%d",&c); update(ll[i],ll[i],1,n,1,c); } scanf("%d",&q); while(q--) { char op[3]; int x,c; scanf("%s",op); if(op[0]=='Q') { scanf("%d",&x); printf("%d\n",query_max(ll[x],rr[x],1,n,1)-query_min(ll[x],rr[x],1,n,1)); } else { scanf("%d%d",&x,&c); update(ll[x],rr[x],1,n,1,c); } } } return 0; }