题目来源： 基准时间限制：1 秒 空间限制：131072 KB 分值: 80
一棵有N个节点的树，每个节点对应1个编号及1个权值，有2种不同的操作。
操作1：S x y z，表示如果编号为x的节点的权值 < y，则将节点x的权值加上z。(Single)
操作2：A x y z，表示如果编号为x的节点以及其所有子节点的权值平均值 < y，则将节点x及其所有子节点的权值加上z。(All)
给出树节点之间的关系，进行M次操作，问所有操作完成后，各个节点的权值为多少？
节点的编号为0 - N - 1，根节点的编号为0，并且初始情况下，根节点的权值也是0。
Input
第1行：2个数N, M，N为节点的数量，M为操作的数量(1 <= N, M <= 50000)。第2 - N行：每行描述一个节点N[i]的信息，第2行对应编号为1的节点，第N行对应编号为N - 1的节点。具体内容为：每行2个数P[i], W[i]。P[i]为当前节点的父节点的编号，W[i]为当前节点的权值。(0 <= W[i] <= 10^5, P[i] < i)第N + 1 - N + M行：每行表示一个操作，S x y z或A x y z，（0 <= y, z <= 10^5)。
Output
输出共N行，每行1个数W[i]，表示经过M次后，编号为0 - N - 1的节点的权值。
Input示例
4 30 100 101 2S 0 1 1A 0 20 1S 3 2 1
Output示例
211113
Analysis分析
求树的DFS序并用线段树维护，经典题型
Code代码
1 #include2 #include 3 #define mid (L+R)/2 4 #define lc (rt<<1) 5 #define rc (rt<<1|1) 6 #define maxn 1000000 7 #define LL long long 8 using namespace std; 9 10 int dfn[maxn],dfl[maxn],TIM,sz[maxn],fa[maxn],n,m; 11 LL vval[maxn],arr[maxn],ans[maxn]; 12 13 struct edge{ 14 int from,v; 15 }e[maxn]; int tot,first[maxn]; 16 void insert(int u,int v){ tot++; e[tot].from = first[u]; e[tot].v = v; first[u] = tot; } 17 18 void dfs(int u){ 19 dfn[u] = ++TIM; 20 arr[TIM] = vval[u]; 21 sz[u] = 1; 22 for(int i = first[u];i;i = e[i].from){ 23 int v = e[i].v; 24 dfs(v); 25 sz[u] += sz[v]; 26 }dfl[u] = TIM; 27 } 28 29 struct node{ 30 LL sum,lazy; 31 }T[maxn*4]; 32 33 void pushdown(int rt,int L,int R){ 34 if(!T[rt].lazy) return; 35 T[lc].lazy += T[rt].lazy; 36 T[rc].lazy += T[rt].lazy; 37 T[lc].sum += T[rt].lazy*(mid-L+1); 38 T[rc].sum += T[rt].lazy*(R-mid); 39 T[rt].lazy = 0; 40 } 41 42 void build(int rt,int L,int R){ // 1,1,TIM 43 if(L == R) T[rt].sum = arr[L]; 44 else{ 45 build(lc,L,mid); build(rc,mid+1,R); 46 T[rt].sum = T[lc].sum+T[rc].sum; 47 } 48 } 49 50 LL query(int rt,int L,int R,int qL,int qR){ 51 pushdown(rt,L,R); 52 if(qL <= L && R <= qR) return T[rt].sum; 53 else{ 54 LL ret = 0; 55 if(qL <= mid) ret += query(lc,L,mid,qL,qR); 56 if(qR > mid) ret += query(rc,mid+1,R,qL,qR); 57 return ret; 58 } 59 } 60 61 void modify(int rt,int L,int R,int qL,int qR,LL val){ 62 pushdown(rt,L,R); 63 if(qL <= L && R <= qR){ 64 T[rt].sum += val*(R-L+1); 65 T[rt].lazy += val; 66 }else{ 67 if(qL <= mid) modify(lc,L,mid,qL,qR,val); 68 if(qR > mid) modify(rc,mid+1,R,qL,qR,val); 69 T[rt].sum = T[lc].sum + T[rc].sum; 70 } 71 } 72 73 void print(int rt,int L,int R){ 74 pushdown(rt,L,R); 75 if(L == R) ans[L] = T[rt].sum; 76 else{ 77 print(lc,L,mid); 78 print(rc,mid+1,R); 79 } 80 } 81 82 void final(){ 83 for(int i = 1;i <= n;i++) printf("%lld\n",ans[dfn[i]]); 84 } 85 86 int main(){ 87 // freopen("1.in","r",stdin); 88 89 scanf("%d%d",&n,&m); 90 91 for(int i = 2;i <= n;i++){ 92 scanf("%d%lld",&fa[i],&vval[i]); 93 insert(fa[i]+1,i); 94 // insert(fa[i],i); 95 } 96 97 dfs(1); 98 build(1,1,TIM); 99 100 for(int i = 1;i <= m;i++){101 char ctr; int x; LL z; double y;102 cin >> ctr; scanf("%d%lf%lld",&x,&y,&z);103 104 x++;105 if(ctr == 'A'){106 LL sum = query(1,1,TIM,dfn[x],dfl[x]);107 if(1.0*sum/(dfl[x]-dfn[x]+1) < y) modify(1,1,TIM,dfn[x],dfl[x],z);108 }else if(1.0*query(1,1,TIM,dfn[x],dfn[x]) < y) modify(1,1,TIM,dfn[x],dfn[x],z);109 // cout << "BBB" << endl;110 }111 112 print(1,1,TIM);113 final();114 115 return 0;116 }