输入文件第一行包含一个数n，表示树的大小。
对于每次询问操作，输出对应的答案，答案之间用换行隔开。
代码：
1 #include<cstdio> 2 #include<cstring> 3 #include<algorithm> 4 #define lll spc<<1 5 #define rrr spc<<1|1 6 typedef long long lnt; 7 const int N=200010; 8 struct trnt{ 9 lnt minv; 10 lnt lzt; 11 }tr[N<<2]; 12 struct pnt{ 13 int hd; 14 int fa; 15 int tp; 16 int dp; 17 int wgt; 18 int mxs; 19 int ind; 20 lnt val; 21 lnt f; 22 lnt sigf; 23 }p[N]; 24 struct ent{ 25 int twd; 26 int lst; 27 }e[N<<1]; 28 int cnt; 29 int n,m; 30 int dfn; 31 int plc[N]; 32 char cmd[100]; 33 void ade(int f,int t) 34 { 35 cnt++; 36 e[cnt].twd=t; 37 e[cnt].lst=p[f].hd; 38 p[f].hd=cnt; 39 return ; 40 } 41 void Basic_dfs(int x,int f) 42 { 43 p[x].fa=f; 44 p[x].dp=p[f].dp+1; 45 p[x].wgt=1; 46 int maxs=-1; 47 for(int i=p[x].hd;i;i=e[i].lst) 48 { 49 int to=e[i].twd; 50 if(to==f) 51 continue; 52 Basic_dfs(to,x); 53 p[x].sigf+=p[to].f; 54 p[x].wgt+=p[to].wgt; 55 if(maxs<p[to].wgt) 56 { 57 maxs=p[to].wgt; 58 p[x].mxs=to; 59 } 60 } 61 if(!p[x].mxs) 62 p[x].sigf=0x3f3f3f3f; 63 p[x].f=std::min(p[x].val,p[x].sigf); 64 return ; 65 } 66 void Build_dfs(int x,int top) 67 { 68 if(!x) 69 return ; 70 p[x].tp=top; 71 p[x].ind=++dfn; 72 plc[dfn]=x; 73 Build_dfs(p[x].mxs,top); 74 for(int i=p[x].hd;i;i=e[i].lst) 75 { 76 int to=e[i].twd; 77 if(p[to].ind) 78 continue; 79 Build_dfs(to,to); 80 } 81 return ; 82 } 83 void pushup(int spc) 84 { 85 tr[spc].minv=std::min(tr[lll].minv,tr[rrr].minv); 86 return ; 87 } 88 void add(int spc,lnt v) 89 { 90 tr[spc].lzt+=v; 91 tr[spc].minv-=v; 92 return ; 93 } 94 void pushdown(int spc) 95 { 96 if(tr[spc].lzt) 97 { 98 add(lll,tr[spc].lzt); 99 add(rrr,tr[spc].lzt); 100 tr[spc].lzt=0; 101 } 102 return ; 103 } 104 void build(int l,int r,int spc) 105 { 106 if(l==r) 107 { 108 tr[spc].minv=p[plc[l]].val-p[plc[l]].sigf; 109 return ; 110 } 111 int mid=(l+r)>>1; 112 build(l,mid,lll); 113 build(mid+1,r,rrr); 114 pushup(spc); 115 return ; 116 } 117 void update(int l,int r,int pos,int spc,lnt v) 118 { 119 if(l==r) 120 { 121 add(spc,-v); 122 return ; 123 } 124 int mid=(l+r)>>1; 125 pushdown(spc); 126 if(pos<=mid) 127 update(l,mid,pos,lll,v); 128 else 129 update(mid+1,r,pos,rrr,v); 130 pushup(spc); 131 return ; 132 } 133 int scupdate(int l,int r,int ll,int rr,int spc,lnt v) 134 { 135 if(l>rr||ll>r) 136 return 0; 137 if(l==r) 138 { 139 add(spc,v); 140 if(tr[spc].minv<=0) 141 return plc[l]; 142 return 0; 143 } 144 if(ll<=l&&r<=rr&&tr[spc].minv>v) 145 { 146 add(spc,v); 147 return 0; 148 } 149 int mid=(l+r)>>1; 150 pushdown(spc); 151 int plcc=scupdate(mid+1,r,ll,rr,rrr,v); 152 if(!plcc) 153 plcc=scupdate(l,mid,ll,rr,lll,v); 154 pushup(spc); 155 return plcc; 156 } 157 lnt query(int l,int r,int pos,int spc) 158 { 159 if(l==r) 160 return tr[spc].minv; 161 int mid=(l+r)>>1; 162 pushdown(spc); 163 if(pos<=mid) 164 return query(l,mid,pos,lll); 165 return query(mid+1,r,pos,rrr); 166 } 167 void Update(int x,lnt v) 168 { 169 if(v<=0||!x) 170 return ; 171 while(x) 172 { 173 int tp=scupdate(1,n,p[p[x].tp].ind,p[x].ind,1,v); 174 if(!tp) 175 x=p[p[x].tp].fa; 176 else{ 177 Update(p[tp].fa,query(1,n,p[tp].ind,1)+v); 178 return ; 179 } 180 } 181 } 182 int main() 183 { 184 scanf("%d",&n); 185 for(int i=1;i<=n;i++) 186 scanf("%d",&p[i].val); 187 for(int i=1;i<n;i++) 188 { 189 int a,b; 190 scanf("%d%d",&a,&b); 191 ade(a,b); 192 ade(b,a); 193 } 194 Basic_dfs(1,1); 195 Build_dfs(1,1); 196 build(1,n,1); 197 scanf("%d",&m); 198 while(m--) 199 { 200 scanf("%s",cmd+1); 201 if(cmd[1]==‘Q‘) 202 { 203 int x; 204 scanf("%d",&x); 205 printf("%lld\n",std::min(p[x].val,p[x].val-query(1,n,p[x].ind,1))); 206 }else{ 207 int x,v; 208 scanf("%d%d",&x,&v); 209 if(!v) 210 continue; 211 p[x].val+=v; 212 update(1,n,p[x].ind,1,v); 213 lnt tmp=p[x].val-query(1,n,p[x].ind,1); 214 p[x].f=std::min(p[x].val,tmp); 215 Update(p[x].fa,p[x].f+v-p[x].val); 216 } 217 } 218 return 0; 219 }
原文：https://www.cnblogs.com/blog-Dr-J/p/10205803.html