一种非 DDP 的树剖做法。
主要是因为我不会 DDP，在考场上只想到了树剖。
首先如果没有修改，很容易想到朴素的 dp 做法：
设 \(val_u\) 表示 \(u\) 本身的权值，\(dp_u\) 表示以 \(u\) 为根的子树的答案，显然有：
就是要么割自己，要么割所有的子树。
为了方便表述，不妨设 \(sum_u=\sum\limits_{v\in son(u)}dp_v\)。
但现在带修了怎么办呢？
DDP？不会！
首先肯定能发现如果修改了一个点 \(u\) 的权值加上了 \(to\)（\(to\geq 0\)），那么最多只有 \(u\) 到根的这条链上的点的 \(dp\) 值会改变。
考虑会做出那些改变：
首先 \(dp_u\) 的变化我们可以计算出来，不妨设 \(dp_u\) 的变化量为 \(x\)，那么对 \(sum_{fa}\) 的贡献也是 \(x\)。（\(fa\) 为 \(u\) 的父亲）
那么如果 \(sum_{fa}+x\leq val_{fa}\)，那么 \(dp_{fa}\) 的变化量也是 \(x\)，那么对 \(fa\) 的父亲 \(gfa\) 的 \(sum_{gfa}\) 的贡献也是 \(x\)。
定义一个函数 \(\operatorname{change}(u,x)\) 表示当 \(sum_u\) 需要增加 \(x\) 时，我们要进行的操作。
下面以 \(\operatorname{change}(fa,x)\) 为例来详细阐述这个操作：
我们从 \(fa\) 开始往上找到第一个不满足 \(sum_v+x\leq val_v\) 的点 \(v\)，即满足 \(sum_v+x> val_v\)，设 \(v\) 向 \(u\) 方向的儿子为 \(son\)，\(v\) 的父亲为 \(f\)。
图大概长这样：
那么按照我们刚才的推论，\(u\) 到 \(son\) 的这一段点的 \(dp\) 值的变化量也都是 \(x\)。
但是当 \(son\) 向 \(sum_v\) 贡献 \(x\) 的时候，发现 \(sum_v+x>val_v\)。接下来分两种情况讨论：
-
若一开始 \(sum_v<val_v\)，加上 \(x\) 后的新的 \(sum_v\) 大于 \(val_v\)，那么 \(dp_v\) 就会变成 \(val_v\)，变化量就是 \(val_v-sum_v\)（这里的 \(sum_v\) 是没有加 \(x\) 之前的 \(sum_v\)），对 \(f\) 的贡献也是 \(val_v-sum_v\)。
那么到这里，我们又可以重复上述过程，进行操作 \(\operatorname{change}(f,val_v-sum_v)\)。
-
若一开始 \(sum_v\leq val_v\)，那么 \(sum_v\) 加上 \(x\) 后对 \(dp_v\) 没有影响（因为 \(dp_v\) 还是 \(val_v\)），那么对 \(v\) 上面的祖先的 \(dp\) 值也不会产生影响。此时直接结束修改就好。
发现上述操作的实质其实就是将 \(rt\) 到 \(u\) 的链分为很多段，然后每一段的 \(dp\) 都是加上同一个权值。
那么现在的问题就变成每一段如何找到段顶 \(v\)，并且还要维护这一段修改 \(sum\) 值。
后面那个很简单，用树剖维护就好，关键是如何找到 \(v\)。
找 \(v\) 和找 \(son\) 是等价的，观察一下 \(son\) 需要满足的要求：\(son\) 是最高的满足从 \(u\) 到 \(son\) 每一个的点 \(i\) 都满足 \(sum_i+x\leq val_i\) 的点。
移一下项，变成：\(x\leq val_i-sum_i\)。
这个时候就好办了，我们用树剖维护每一个点的 \(val-sum\)，然后在线段树中维护每个区间的最小值：只有当一个区间的最小值大于等于 \(x\) 时，这个区间的所有值都大于等于 \(x\)。
那么就能按这种方法在线段树上找到 \(son\)，然后 \(v\) 就是 \(son\) 的父亲了。
发现我们还能同时在这棵线段树上通过修改 \(val-sum\) 的值来修改 \(sum\) 的值，很方便。
那么询问的时候答案就是 \(\min(val_u,val_u-\operatorname{query}(u))\)。（这里的 \(\operatorname{query}(u)\) 其实就是在线段树中查询到的 \(val_u-sum_u\)）
至于时间为什么能够保证：
首先一次修改的时间取决于分成的段数，因为每一段都是 \(O(\log n)\) 的。
发现一次修改有可能就一段，有可能有 \(n\) 段，所以要从总体考虑这个事情。
考虑将分段的个数转化为每一个点 \(v\) 被分成段头的次数：
如果一个点 \(v\) 被分成段头，那么肯定是出现了 \(sum_v\leq val_v\) 但 \(sum_v+x>val_v\) 的情况，那么加上 \(x\) 后的新的 \(sum_v\) 会大于 \(val_v\)。又由于每一次修改操作都是给一个点的权值加上非负整数 \(x\)，所以对 \(sum\) 的贡献也是非负整数。
所以除非修改自己的点权 \(val_v\)，在第一次 \(sum_v>val_v\) 后，\(v\) 就不会被分为链头。又由于只有当 \(sum_v\leq val_v\) 且 \(sum_v+x>val_v\) 的情况下 \(v\) 会被分为链头，所以每一个点最多只会被分为链头一次，所以段数不会大于 \(n\) 级别。
那么总时间复杂度就是 \(O((n+m)\log^2 n)\)，可以通过。
代码如下，有很多细节：
#include<bits/stdc++.h>
#define N 200010
#define INF 0x7fffffffffffffff
#define ll long long
using namespace std;
int n,m;
int cnt,head[N],nxt[N<<1],to[N<<1];
int idx,fa[N],size[N],son[N],id[N],rk[N],top[N];
ll val[N],sumson[N],dp[N];
ll minn[N<<2],lazy[N<<2],mostl[N<<2];
void adde(int u,int v)
{
to[++cnt]=v;
nxt[cnt]=head[u];
head[u]=cnt;
}
void dfs(int u)
{
size[u]=1;
bool leaf=true;
for(int i=head[u];i;i=nxt[i])
{
int v=to[i];
if(v==fa[u]) continue;
leaf=false;
fa[v]=u;
dfs(v);
sumson[u]+=dp[v];
size[u]+=size[v];
if(size[v]>size[son[u]]) son[u]=v;
}
if(leaf) sumson[u]=INF/100,dp[u]=val[u];
else dp[u]=min(val[u],sumson[u]);
}
void dfs1(int u,int tp)
{
top[u]=tp;
id[u]=++idx;
rk[idx]=u;
if(son[u]) dfs1(son[u],tp);
for(int i=head[u];i;i=nxt[i])
if(to[i]!=fa[u]&&to[i]!=son[u])
dfs1(to[i],to[i]);
}
void up(int k)
{
minn[k]=min(minn[k<<1],minn[k<<1|1]);
}
void downn(int k,ll v)
{
minn[k]-=v;
lazy[k]+=v;
}
void down(int k)
{
if(lazy[k])
{
downn(k<<1,lazy[k]);
downn(k<<1|1,lazy[k]);
lazy[k]=0;
}
}
void build(int k,int l,int r)
{
if(l==r)
{
minn[k]=val[rk[l]]-sumson[rk[l]];
mostl[k]=rk[l];
return;
}
int mid=(l+r)>>1;
build(k<<1,l,mid);
build(k<<1|1,mid+1,r);
mostl[k]=mostl[k<<1];
up(k);
}
ll query(int k,int l,int r,int x)
{
if(l==r) return minn[k];
down(k);
int mid=(l+r)>>1;
if(x<=mid) return query(k<<1,l,mid,x);
return query(k<<1|1,mid+1,r,x);
}
void update(int k,int l,int r,int ql,int qr,ll v)
{
if(ql<=l&&r<=qr)
{
downn(k,v);
return;
}
down(k);
int mid=(l+r)>>1;
if(ql<=mid) update(k<<1,l,mid,ql,qr,v);
if(qr>mid) update(k<<1|1,mid+1,r,ql,qr,v);
up(k);
}
int find(int k,int l,int r,int ql,int qr,ll v)//找到son
{
if(ql<=l&&r<=qr&&minn[k]>=v) return mostl[k];
if(l==r) return -1;
down(k);
int mid=(l+r)>>1;
if(qr>mid)
{
int ans2=find(k<<1|1,mid+1,r,ql,qr,v);
if(ans2==mostl[k<<1|1]&&ql<=mid)
{
int ans1=find(k<<1,l,mid,ql,qr,v);
if(ans1==-1) return ans2;
return ans1;
}
return ans2;
}
return find(k<<1,l,mid,ql,qr,v);
}
void work(int u,ll v)
{
ll t=query(1,1,n,id[u]);
val[u]+=v,update(1,1,n,id[u],id[u],-v);
if(t>=0) return;
if(t+v>0) v=-t;
u=fa[u];
while(u)
{
int tmp=find(1,1,n,id[top[u]],id[u],v);//这里的tmp就是son
while(tmp==top[u])
{
update(1,1,n,id[tmp],id[u],v);
u=fa[tmp];
if(!u) return;
tmp=find(1,1,n,id[top[u]],id[u],v);
}
if(tmp==-1)
{
ll t=query(1,1,n,id[u]);
update(1,1,n,id[u],id[u],v);
if((v=t)<=0) return;
u=fa[u];
continue;
}
ll t=query(1,1,n,id[fa[tmp]]);
update(1,1,n,id[fa[tmp]],id[u],v);
if((v=t)<=0) return;
u=fa[fa[tmp]];
}
}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
scanf("%lld",&val[i]);
for(int i=1;i<n;i++)
{
int u,v;
scanf("%d%d",&u,&v);
adde(u,v),adde(v,u);
}
dfs(1),dfs1(1,1);
build(1,1,n);
scanf("%d",&m);
int Q=0;
while(m--)
{
char opt[2];
scanf("%s",opt);
if(opt[0]=='Q')
{
Q++;
int u;
scanf("%d",&u);
printf("%lld\n",min(val[u],val[u]-query(1,1,n,id[u])));
}
else
{
int u;ll v;
scanf("%d%lld",&u,&v);
work(u,v);
}
}
return 0;
}
原文地址：http://www.cnblogs.com/ez-lcw/p/16837305.html
