[BZOJ5212][ZJOI2018]历史

人生第一道九条可怜……神仙操作……

看着题解理解了一个早上才勉强看懂怎么回事……

简化一下题目就是：已知每一个点access的总次数，求一个顺序使虚实边转化的次数最多

考虑一下，对于x的一个子树，如果他已经有了一个最优序列，那么一定不会和他祖先的最优序列产生冲突。为什么呢？因为对他的所有祖先来说，只要是来自他的子树的access都会对他到根的路径产生贡献，所以对他的祖先来说，无论access的是子树的哪一个节点都是等价的，于是我们可以在祖先的最优序列中将所有x的子树的access调换位置，并不会影响最优解

于是单独考虑每一个点x，只有x的子树以及x本身的access会对x的实子边产生影响（x的access会是x没有实子边），如果切换的两点不在x的同一子树（或都是x），每切换一次答案+1，。于是我们可以转化为这么一个问题，有$sum[x]$个球（表示x及他的子树总共有多少次access操作），每种颜色的球有$sum[c]$个（表示x的每一个子树以及x本身的操作次数），求一种排列，使他们两两相邻颜色不同的对数最大。很明显，如果没有一种球的出现次数大于球的总数的一半，那么答案就是$sum[x]-1$，否则的话，出现次数大于一半的球必定有某几对不会对答案产生贡献，答案就是$2*(sum[x]-max(sum[c]))$

当$sum[c]*2>sum[x]+1$时取后者

直接树形dp就行了

然后考虑一下怎么修改呢？

首先，对某一个点的修改，只会对该点到根的路径上的答案有影响

因为是加一个值，如果有一个点的子树$sum$大于父节点$sum$的一半，那么代入上式可以发现答案是不变的

那么我们是不是可以用树剖的思路？对于子树$sum$大于自己$sum$一半的点连实边，其余的连虚边，然后access的时候更改虚实边即可

为了方便计算以前的贡献，可以保存一下以前贡献的类型（某子树过大、自己过大、都不是很大）算的时候就省去了一些判断的时间。

 //minamoto

 #include<cstdio>

 #include<iostream>

 #define ll long long

 #define getc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)

 char buf[<<],*p1=buf,*p2=buf;

 template<class T>inline bool cmax(T&a,const T&b){return a<b?a=b,:;}

 inline int read(){

     #define num ch-'0'

     char ch;bool flag=;int res;

     while(!isdigit(ch=getc()))

     (ch=='-')&&(flag=true);

     for(res=num;isdigit(ch=getc());res=res*+num);

     (flag)&&(res=-res);

     #undef num

     return res;

 }

 char obuf[<<],*o=obuf;

 void print(ll x){

     if(x>) print(x/);

     *o++=x%+;

 }

 const int N=,M=N*;

 int ver[M],Next[M],head[N],tot;

 int fa[N],ch[N][];short tp[N];

 ll sum[N],si[N],a[N],ans;

 inline bool isroot(int x){return ch[fa[x]][]!=x&&ch[fa[x]][]!=x;}

 #define lc ch[x][0]

 #define rc ch[x][1]

 inline void pushup(int x){sum[x]=sum[lc]+sum[rc]+si[x]+a[x];}

 inline void rotate(int x){

     int y=fa[x],z=fa[y],d=ch[y][]==x;

     if(!isroot(y)) ch[z][ch[z][]==y]=x;

     fa[x]=z,fa[y]=x,fa[ch[x][d^]]=y,ch[y][d]=ch[x][d^],ch[x][d^]=y,pushup(y);

 }

 inline void splay(int x){

     for(int y=fa[x],z=fa[y];!isroot(x);y=fa[x],z=fa[y]){

         if(!isroot(y))

         ((ch[y][]==x)^(ch[z][]==y))?rotate(x):rotate(y);

         rotate(x);

     }

     pushup(x);

 }

 void dp(int x){

     int mp=x;ll mx=a[x];

     for(int i=head[x];i;i=Next[i]){

         int v=ver[i];

         if(v==fa[x]) continue;

         fa[v]=x,dp(v);

         si[x]+=sum[v];

         if(mx<sum[v]) mp=v,mx=sum[v];

     }

     if((mx<<)>(sum[x]=si[x]+a[x])){

         ans+=(sum[x]-mx)<<;

         x==mp?tp[x]=:si[x]-=sum[rc=mp];

     }

     else tp[x]=,ans+=sum[x]-;

 }

 int main(){

     //freopen("testdata.in","r",stdin);

     int n=read(),m=read();

     for(int i=;i<=n;++i) a[i]=read();

     for(int i=;i<n;++i){

             int u=read(),v=read();

         ver[++tot]=v,Next[tot]=head[u],head[u]=tot;

         ver[++tot]=u,Next[tot]=head[v],head[v]=tot;

     }

     dp();print(ans),*o++='\n';

     while(m--){

         int x=read(),w=read();

         for(int y=;x;x=fa[y=x]){

             splay(x);

             ll s=sum[x]-sum[lc];

             ans-=tp[x]<?(s-(tp[x]?a[x]:sum[rc]))<<:s-;

             s+=w,sum[x]+=w,(y?si:a)[x]+=w;

             if(sum[y]<<>s) si[x]+=sum[rc],si[x]-=sum[rc=y];

             if(sum[rc]<<>s) tp[x]=,ans+=(s-sum[rc])<<;

             else{

                 if(rc) si[x]+=sum[rc],rc=;

                 (a[x]<<>s)?(tp[x]=,ans+=(s-a[x])<<):(tp[x]=,ans+=s-,rc=);

             }

         }

         print(ans),*o++='\n';

     }

     fwrite(obuf,o-obuf,,stdout);

     return ;

 }

巴特西

[BZOJ5212][ZJOI2018]历史

最新文章

热门文章