题解：
注意题目说了每个点的权值只能增加
每个点的dp方程比较简单 min(v[i],sum[i])
那么我们考虑如果v[i]增加那么上面使用sum[i]的会带来影响
暴力的做就是一个个往上查然后修改
比较显然的是这个东西可以二分
我们维护v[i]-sum[i]的值，查到那个不符合的就可以了
这样我们就变成了花log^2n的时间对v[i]>sum[i]的变成v[i]<sum[i]
而每次操作最多增加一个v[i]>sum[i]
所以复杂度是对的
树链剖分维护，复杂度nlog^2n
还是比较考验代码能力的
树剖那里一定要理清楚思路
代码：
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define rint register ll
#define rll register ll
#define IL inline
#define rep(i,h,t) for (rint i=h;i<=t;i++)
#define dep(i,t,h) for (rint i=t;i>=h;i--)
const ll N=2e5+1e4;
const ll N2=N*;
const ll INF=1e9;
ll n,m,v[N],head[N],id[N],rel[N],yz[N],fa[N],f[N],son[N],g[N],num[N],top[N],l;
ll data[N2],cnt,lazy[N2];
struct re{
ll a,b,c;
}e[N*];
void arr(ll x,ll y)
{
e[++l].a=head[x];
e[l].b=y;
head[x]=l;
}
void dfs(ll x,ll y)
{
f[x]=v[x]; num[x]=; fa[x]=y;
ll sum=;
for (rint u=head[x];u;u=e[u].a)
{
rint v=e[u].b;
if (v!=y)
{
yz[x]=;
dfs(v,x);
sum+=f[v];
num[x]+=num[v];
if (num[v]>num[son[x]]) son[x]=v;
}
}
if (sum) f[x]=min(f[x],sum);
if (sum) g[x]=sum; else g[x]=f[x];
}
void dfs2(ll x,ll y,ll z)
{
id[x]=++cnt; rel[cnt]=x;
top[x]=y;
if (!son[x]) return;
dfs2(son[x],y,x);
for (rint u=head[x];u;u=e[u].a)
{
rint v=e[u].b;
if (v!=z&&v!=son[x]) dfs2(v,v,x);
}
}
#define updata(x) data[x]=min(data[x*2],data[x*2+1])
#define mid ((h+t)/2)
IL void down(ll x)
{
if (!lazy[x]) return;
lazy[x*]+=lazy[x]; lazy[x*+]+=lazy[x];
data[x*]-=lazy[x]; data[x*+]-=lazy[x];
lazy[x]=;
}
void build(ll x,ll h,ll t)
{
if (h==t)
{
data[x]=v[rel[h]]-g[rel[h]];
return;
}
build(x*,h,mid); build(x*+,mid+,t);
updata(x);
}
ll query(ll x,ll h,ll t,ll pos)
{
if (h==t)
{
if (data[x]>) return(v[rel[h]]-data[x]);
else return(v[rel[h]]);
}
down(x);
if (pos<=mid) return(query(x*,h,mid,pos));
else return(query(x*+,mid+,t,pos));
updata(x);
}
void change2(ll x,ll h,ll t,ll h1,ll t1,ll k)
{
if (h1<=h&&t<=t1)
{
lazy[x]+=k; data[x]-=k; return;
}
down(x);
if (h1<=mid) change2(x*,h,mid,h1,t1,k);
if (mid<t1) change2(x*+,mid+,t,h1,t1,k);
updata(x);
}
ll query2(ll x,ll h,ll t,ll h1,ll t1)
{
if (h1<=h&&t<=t1)
{
return(data[x]);
}
down(x);
ll ans=INF;
if (h1<=mid) ans=min(ans,query2(x*,h,mid,h1,t1));
if (mid<t1) ans=min(ans,query2(x*+,mid+,t,h1,t1));
return(ans);
}
vector<re> ve;
void find2(ll x,ll h,ll t,ll h1,ll t1)
{
if (h1<=h&&t<=t1)
{
ve.push_back((re){x,h,t}); return;
}
down(x);
if (h1<=mid) find2(x*,h,mid,h1,t1);
if (mid<t1) find2(x*+,mid+,t,h1,t1);
}
ll find3(ll x,ll h,ll t,ll k)
{
if (h==t) return(h);
down(x);
if (data[x*+]<k) return(find3(x*+,mid+,t,k));
else return(find3(x*,h,mid,k));
}
void change(rll x,rll y)
{
if (!y) return;
rll now=x;
while (top[now])
{
if (query2(,,n,id[top[now]],id[now])>=y)
{
change2(,,n,id[top[now]],id[now],y); //v[x]-g[x] 减小y
} else
{
ve.clear();
find2(,,n,id[top[now]],id[now]);
rll l=int(ve.size())-;
rll k;
dep(i,l,)
if (data[ve[i].a]<y)
{
k=find3(ve[i].a,ve[i].b,ve[i].c,y); // k.a 位置 k.b v[x]-g[x]
break;
}
rll x1=query(,,n,k);
change2(,,n,k,id[now],y);
rll x2=query(,,n,k);
change(fa[rel[k]],x2-x1);
break;
}
now=fa[top[now]];
}
}
int main()
{
freopen("1.in","r",stdin);
freopen("1.out","w",stdout);
ios::sync_with_stdio(false);
cin>>n;
rep(i,,n) cin>>v[i];
rep(i,,n-)
{
ll x,y; cin>>x>>y;
arr(x,y); arr(y,x);
}
dfs(,);
dfs2(,,);
build(,,n);
cin>>m;
char cc;
rep(i,,m)
{
ll x,y;
cin>>cc;
if (cc=='Q')
{
cin>>x;
cout<<query(,,n,id[x])<<endl;
} else
{
cin>>x>>y;
ll x1=query(,,n,id[x]);
v[x]+=y;
if (yz[x])
{
change2(,,n,id[x],id[x],-y);
ll x3=query(,,n,id[x]);
if (x3>x1) change(fa[x],x3-x1);
}
else change(fa[x],y);
}
}
return ;
}