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
4 3 2 1
1 2
1 3
4 2
4
Q 1
Q 2
C 4 10
Q 1
4 3 2 1
1 2
1 3
4 2
4
Q 1
Q 2
C 4 10
Q 1
Sample Output
3
1
4
1
4
解题思路：
代码：
#include<cstdio>
#include<cstring>
#include<algorithm>
#define lll spc<<1
#define rrr spc<<1|1
typedef long long lnt;
const int N=;
struct trnt{
lnt minv;
lnt lzt;
}tr[N<<];
struct pnt{
int hd;
int fa;
int tp;
int dp;
int wgt;
int mxs;
int ind;
lnt val;
lnt f;
lnt sigf;
}p[N];
struct ent{
int twd;
int lst;
}e[N<<];
int cnt;
int n,m;
int dfn;
int plc[N];
char cmd[];
void ade(int f,int t)
{
cnt++;
e[cnt].twd=t;
e[cnt].lst=p[f].hd;
p[f].hd=cnt;
return ;
}
void Basic_dfs(int x,int f)
{
p[x].fa=f;
p[x].dp=p[f].dp+;
p[x].wgt=;
int maxs=-;
for(int i=p[x].hd;i;i=e[i].lst)
{
int to=e[i].twd;
if(to==f)
continue;
Basic_dfs(to,x);
p[x].sigf+=p[to].f;
p[x].wgt+=p[to].wgt;
if(maxs<p[to].wgt)
{
maxs=p[to].wgt;
p[x].mxs=to;
}
}
if(!p[x].mxs)
p[x].sigf=0x3f3f3f3f;
p[x].f=std::min(p[x].val,p[x].sigf);
return ;
}
void Build_dfs(int x,int top)
{
if(!x)
return ;
p[x].tp=top;
p[x].ind=++dfn;
plc[dfn]=x;
Build_dfs(p[x].mxs,top);
for(int i=p[x].hd;i;i=e[i].lst)
{
int to=e[i].twd;
if(p[to].ind)
continue;
Build_dfs(to,to);
}
return ;
}
void pushup(int spc)
{
tr[spc].minv=std::min(tr[lll].minv,tr[rrr].minv);
return ;
}
void add(int spc,lnt v)
{
tr[spc].lzt+=v;
tr[spc].minv-=v;
return ;
}
void pushdown(int spc)
{
if(tr[spc].lzt)
{
add(lll,tr[spc].lzt);
add(rrr,tr[spc].lzt);
tr[spc].lzt=;
}
return ;
}
void build(int l,int r,int spc)
{
if(l==r)
{
tr[spc].minv=p[plc[l]].val-p[plc[l]].sigf;
return ;
}
int mid=(l+r)>>;
build(l,mid,lll);
build(mid+,r,rrr);
pushup(spc);
return ;
}
void update(int l,int r,int pos,int spc,lnt v)
{
if(l==r)
{
add(spc,-v);
return ;
}
int mid=(l+r)>>;
pushdown(spc);
if(pos<=mid)
update(l,mid,pos,lll,v);
else
update(mid+,r,pos,rrr,v);
pushup(spc);
return ;
}
int scupdate(int l,int r,int ll,int rr,int spc,lnt v)
{
if(l>rr||ll>r)
return ;
if(l==r)
{
add(spc,v);
if(tr[spc].minv<=)
return plc[l];
return ;
}
if(ll<=l&&r<=rr&&tr[spc].minv>v)
{
add(spc,v);
return ;
}
int mid=(l+r)>>;
pushdown(spc);
int plcc=scupdate(mid+,r,ll,rr,rrr,v);
if(!plcc)
plcc=scupdate(l,mid,ll,rr,lll,v);
pushup(spc);
return plcc;
}
lnt query(int l,int r,int pos,int spc)
{
if(l==r)
return tr[spc].minv;
int mid=(l+r)>>;
pushdown(spc);
if(pos<=mid)
return query(l,mid,pos,lll);
return query(mid+,r,pos,rrr);
}
void Update(int x,lnt v)
{
if(v<=||!x)
return ;
while(x)
{
int tp=scupdate(,n,p[p[x].tp].ind,p[x].ind,,v);
if(!tp)
x=p[p[x].tp].fa;
else{
Update(p[tp].fa,query(,n,p[tp].ind,)+v);
return ;
}
}
}
int main()
{
scanf("%d",&n);
for(int i=;i<=n;i++)
scanf("%d",&p[i].val);
for(int i=;i<n;i++)
{
int a,b;
scanf("%d%d",&a,&b);
ade(a,b);
ade(b,a);
}
Basic_dfs(,);
Build_dfs(,);
build(,n,);
scanf("%d",&m);
while(m--)
{
scanf("%s",cmd+);
if(cmd[]=='Q')
{
int x;
scanf("%d",&x);
printf("%lld\n",std::min(p[x].val,p[x].val-query(,n,p[x].ind,)));
}else{
int x,v;
scanf("%d%d",&x,&v);
if(!v)
continue;
p[x].val+=v;
update(,n,p[x].ind,,v);
lnt tmp=p[x].val-query(,n,p[x].ind,);
p[x].f=std::min(p[x].val,tmp);
Update(p[x].fa,p[x].f+v-p[x].val);
}
}
return ;
}