题目大意,大致就是给出一棵有根数,给出每个点access的次数,要你安排顺序,求轻重边切换最多多少次,动态加次数.
第一步其实还挺好想的,思考一下如何静态做,发现相当于对于每一个节点,就是让各个子树的权值和 和 自己的access次数互插,使得相邻两个不同的个数越多越好,这个东西想一想就可以知道答案是,其中x是最大的个数,具体怎么得来,可以直接分类讨论(x>n/2 x=n/2 x<n/2)三种情况,笔者不多赘述.
第二步才是有意思的地方,我们可以在x>n/2时连实边,否则连虚边,然后用类似LCT一样维护实边构成的spaly.每次access实边的答案都不会变因为x,n都增加了,虚边可能会变成实边,也有可能将原来的实边断掉,分类讨论即可.这样每次跳虚边,子树权值和必定翻倍,那么总跳跃次数就是log ai总和.每次要进行一次splay,那么复杂度就是两个log.
#include<bits/stdc++.h> #define ls son[x][0] #define rs son[x][1] using namespace std; const int N=450010; int n,m; struct edge{ int y,next; }s[N<<1]; int first[N],len=0,fa[N],lazy[N],sta[N]; long long sum[N],val[N],S[N]; int son[N][2]; long long ans=0; void ins(int x,int y){ s[++len]=(edge){y,first[x]};first[x]=len; s[++len]=(edge){x,first[y]};first[y]=len; } bool nrt(int x){ return !(son[fa[x]][0]!=x && son[fa[x]][1]!=x); } void update(int x){ sum[x]=val[x]+S[x]+sum[ls]+sum[rs]; } void dfs(int x){ long long mmax=val[x]; int p=0; for(int i=first[x];i!=0;i=s[i].next) if(s[i].y!=fa[x]){ int y=s[i].y;fa[y]=x;dfs(y); S[x]+=sum[y]; if(sum[y]>mmax) mmax=sum[y],p=y; } if(2*mmax>=val[x]+S[x]+1 && p) S[x]-=mmax,son[x][1]=p; update(x); ans+=min(sum[x]-1,2*(sum[x]-mmax)); } void rotate(int x){ int f=fa[x],ff=fa[f],w=(son[f][0]==x); fa[x]=ff;fa[f]=x;if(son[x][w]) fa[son[x][w]]=f; if(son[ff][0]==f) son[ff][0]=x; else if(son[ff][1]==f) son[ff][1]=x; son[f][1-w]=son[x][w];son[x][w]=f; update(f);update(x); } void splay(int x){ while(nrt(x)){ if(nrt(fa[x])){ if((son[fa[x]][0]==x) ^ (son[fa[fa[x]]][0]==fa[x])) rotate(x); else rotate(fa[x]); } rotate(x); } } void access(int x,int t){ splay(x); long long Sum=sum[x]-sum[ls]; ans-=min(Sum-1,2*(Sum-max(sum[rs],val[x]))); val[x]+=t;sum[x]+=t;Sum+=t; ans+=min(Sum-1,2*(Sum-max(sum[rs],val[x]))); if(sum[rs]*2<Sum+1) S[x]+=sum[rs],rs=0; int last=x;x=fa[x]; while(x){ splay(x); Sum=sum[x]-sum[ls]; ans-=min(Sum-1,2*(Sum-max(sum[rs],val[x]))); sum[x]+=t;S[x]+=t;Sum+=t; ans+=min(Sum-1,2*(Sum-max(sum[last],max(val[x],sum[rs])))); if(sum[last]*2>=Sum+1) S[x]-=sum[last],S[x]+=sum[rs],rs=last; else if(sum[rs]*2<Sum+1) S[x]+=sum[rs],rs=0; last=x;x=fa[x]; } } int main(){ scanf("%d %d",&n,&m); for(int i=1;i<=n;i++) scanf("%lld",&val[i]); int x,y; for(int i=1;i<n;i++) scanf("%d %d",&x,&y),ins(x,y); fa[1]=0;dfs(1); printf("%lld\n",ans); while(m--){ scanf("%d %d",&x,&y); access(x,y); printf("%lld\n",ans); } }
