Description

小A走到一个山脚下，准备给自己造一个小屋。这时候，小A的朋友（op，又叫管理员）打开了创造模式，然后飞到

山顶放了格水。于是小A面前出现了一个瀑布。作为平民的小A只好老实巴交地爬山堵水。那么问题来了：我们把这

个瀑布看成是一个n个节点的树，每个节点有权值（爬上去的代价）。小A要选择一些节点，以其权值和作为代价将

这些点删除（堵上），使得根节点与所有叶子结点不连通。问最小代价。不过到这还没结束。小A的朋友觉得这样

子太便宜小A了，于是他还会不断地修改地形，使得某个节点的权值发生变化。不过到这还没结束。小A觉得朋友做

得太绝了，于是放弃了分离所有叶子节点的方案。取而代之的是，每次他只要在某个子树中（和子树之外的点完全

无关）。于是他找到你。

Input

输入文件第一行包含一个数n，表示树的大小。

接下来一行包含n个数，表示第i个点的权值。

接下来n-1行每行包含两个数fr，to。表示书中有一条边（fr，to）。

接下来一行一个整数，表示操作的个数。

接下来m行每行表示一个操作，若该行第一个数为Q，则表示询问操作，后面跟一个参数x，表示对应子树的根；若

为C，则表示修改操作，后面接两个参数x，to，表示将点x的权值加上to。

n<=200000，保证任意to都为非负数

Output

对于每次询问操作，输出对应的答案，答案之间用换行隔开。

Sample Input

4 3 2 1

1 2

1 3

4 2

Q 1

Q 2

C 4 10

Q 1

Sample Output

解题思路：

代码：

1 #include
     
        2 #include
      
         3 #include
       
          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
        
         >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     else129         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