BZOJ4712 : 洪水

首先不难列出DP方程：

$dp[x]=\min(w[x],h[x])$

$h[x]=\sum dp[son]$

当$w[x]$增加时，显然$dp[x]$不会减少，那么我们求出$dp[x]$的增量$delta$，若$delta=0$那么什么都不需要做。

对于$x$来说，它的$h$值不变。

对于$x$的父亲$y$到某个祖先$z$路径上的所有点来说，它们都满足$h[i]+delta\leq w[i]$，那么这些点的$h$值都要加上$delta$。

对于$u=father[z]$来说，这个点的$h$值也要加上$delta$，但是要重新计算DP值。

这将形成一个循环的过程，不断对$h$数组进行修正即可。

为了得到$z$，需要沿着重链往上爬，对于每条重链在线段树中二分查找。

如果一个区间内$\min(w[i]-h[i])\geq delta$，那么整段区间都可行。

因此在线段树上每个点维护两个值：

$val$：$\min(w[i]-h[i])$

$tag$：区间内所有点$h$值要加上多少

对于叶子节点来说，$tag$实际上就是$h$值，因此不需要额外维护$h$值。

一个点要重新计算DP值，当且仅当它的孩子的总代价超过了自己本身的$w$，并且一旦超过，在下次修改这个点的$w$之前DP值将一直是$w$。

因此每个点一开始会贡献一个可能的重新计算次数，每次修改也会贡献一个。

而暴力修改的次数不会超过所有操作贡献的可能导致暴力的次数，所以暴力次数为$O(n+m)$。

总时间复杂度$O((n+m)\log^2n)$。

#include<cstdio>

typedef long long ll;

const int N=200010,M=524300;

const ll inf=1LL<<60;

char op;

int n,m,i,x,y,g[N],v[N<<1],nxt[N<<1],ed;

int f[N],size[N],son[N],top[N],loc[N],q[N],dfn;

ll w[N],z,dp[N],h[N],val[M],tag[M];

inline void read(int&a){char c;while(!(((c=getchar())>='0')&&(c<='9')));a=c-'0';while(((c=getchar())>='0')&&(c<='9'))(a*=10)+=c-'0';}

inline void read(ll&a){char c;while(!(((c=getchar())>='0')&&(c<='9')));a=c-'0';while(((c=getchar())>='0')&&(c<='9'))(a*=10)+=c-'0';}

inline void add(int x,int y){v[++ed]=y;nxt[ed]=g[x];g[x]=ed;}

inline ll min(ll a,ll b){return a<b?a:b;}

void dfs(int x){

  size[x]=1;

  for(int i=g[x];i;i=nxt[i])if(v[i]!=f[x]){

    f[v[i]]=x;

    dfs(v[i]);

    size[x]+=size[v[i]];

    h[x]+=dp[v[i]];

    if(size[v[i]]>size[son[x]])son[x]=v[i];

  }

  if(size[x]==1)h[x]=inf;

  dp[x]=min(w[x],h[x]);

}

void dfs2(int x,int y){

  q[loc[x]=++dfn]=x;top[x]=y;

  if(son[x])dfs2(son[x],y);

  for(int i=g[x];i;i=nxt[i])if(v[i]!=son[x]&&v[i]!=f[x])dfs2(v[i],v[i]);

}

inline void tag1(int x,ll p){val[x]-=p;tag[x]+=p;}

inline void pb(int x){if(tag[x])tag1(x<<1,tag[x]),tag1(x<<1|1,tag[x]),tag[x]=0;}

inline void up(int x){val[x]=min(val[x<<1],val[x<<1|1]);}

void build(int x,int a,int b){

  if(a==b){

    int y=q[a];

    val[x]=w[y]-h[y];

    tag[x]=h[y];

    return;

  }

  int mid=(a+b)>>1;

  build(x<<1,a,mid),build(x<<1|1,mid+1,b);

  up(x);

}

ll ask(int x,int a,int b,int c){

  if(a==b)return tag[x];

  pb(x);

  int mid=(a+b)>>1;

  return c<=mid?ask(x<<1,a,mid,c):ask(x<<1|1,mid+1,b,c);

}

void changew(int x,int a,int b,int c){

  if(a==b){val[x]=w[q[a]]-tag[x];return;}

  pb(x);

  int mid=(a+b)>>1;

  if(c<=mid)changew(x<<1,a,mid,c);else changew(x<<1|1,mid+1,b,c);

  up(x);

}

void changeh(int x,int a,int b,int c,int d,ll p){

  if(c<=a&&b<=d){tag1(x,p);return;}

  pb(x);

  int mid=(a+b)>>1;

  if(c<=mid)changeh(x<<1,a,mid,c,d,p);

  if(d>mid)changeh(x<<1|1,mid+1,b,c,d,p);

  up(x);

}

int get(int x,int a,int b,int c,int d,ll p){

  if(c<=a&&b<=d){

    if(val[x]>=p)return a;

    if(a==b)return 0;

  }

  pb(x);

  int mid=(a+b)>>1,t;

  if(d<=mid)return get(x<<1,a,mid,c,d,p);

  if(c>mid)return get(x<<1|1,mid+1,b,c,d,p);

  t=get(x<<1|1,mid+1,b,c,d,p);

  if(!t||t>mid+1)return t;

  t=get(x<<1,a,mid,c,d,p);

  return t?t:mid+1;

}

inline ll DP(int x){return min(w[x],ask(1,1,n,loc[x]));}

inline int gety(int x,ll p){

  int t=x;x=f[x];

  while(x){

    int o=get(1,1,n,loc[top[x]],loc[x],p);

    if(!o)break;

    if(o>loc[top[x]])return q[o];

    t=top[x];

    x=f[t];

  }

  return t;

}

inline void chain(int x,int y,ll p){

  while(top[x]!=top[y])changeh(1,1,n,loc[top[x]],loc[x],p),x=f[top[x]];

  changeh(1,1,n,loc[y],loc[x],p);

}

inline void modify(int x,ll y){

  ll t=DP(x);

  w[x]+=y;

  changew(1,1,n,loc[x]);

  ll d=DP(x)-t;

  if(!d)return;

  while(f[x]){

    int y=gety(x,d);

    if(x!=y)chain(f[x],y,d);

    x=f[y];

    if(!x)return;

    t=DP(x);

    chain(x,x,d);

    d=DP(x)-t;

    if(!d)return;

  }

}

int main(){

  read(n);

  for(i=1;i<=n;i++)read(w[i]);

  for(i=1;i<n;i++)read(x),read(y),add(x,y),add(y,x);

  dfs(1);dfs2(1,1);

  build(1,1,n);

  read(m);

  while(m--){

    while((op=getchar())!='Q'&&op!='C');read(x);

    if(op=='Q')printf("%lld\n",DP(x));else read(z),modify(x,z);

  }

  return 0;

}

巴特西

BZOJ4712 : 洪水

最新文章

热门文章