Description:
给定一棵树,定义每个点的操作为把这个点到1号点的路径覆盖上颜色i,每次该点到1号点经过的不同颜色段数会加到答案中,要使所有点按某一顺序操作完后答案最大
给定每个点要执行的操作次数,并给出m次修改,问每次修改后的最大答案
Hint:
\(n,m \le 4*10^5\)
Solution:
其实主要是要想到这个结论,注意我们可以分别算每个点的答案,再加起来
考虑对于i点的子树,如何让答案更优?
就是要使那些在不同儿子中的点轮流依次操作
实际上有个结论:
如果有一个儿子子树\(size\)小于等于\((sz[i]+1)/2\),则答案就是\(sz[i]-1\)
否则就是\((sz[i]-sz[v])*2\)
这个想想还是很好理解的
于是我们可以把LCT实虚链切换的条件改一下,改成上述
这样每次修改时能方便的维护之前的答案类型
其实这题的LCT只起了一个维持平衡的作用......
代码细节稍多
#include <map>
#include <set>
#include <stack>
#include <cmath>
#include <queue>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#define ls p<<1
#define rs p<<1|1
using namespace std;
typedef long long ll;
const int mxn=4e5+5;
int n,m,cnt,hd[mxn];
ll ans;inline int read() {char c=getchar(); int x=0,f=1;while(c>'9'||c<'0') {if(c=='-') f=-1;c=getchar();}while(c<='9'&&c>='0') {x=(x<<3)+(x<<1)+(c&15);c=getchar();}return x*f;
}
inline int chkmax(int &x,int y) {if(x<y) x=y;}
inline int chkmin(int &x,int y) {if(x>y) x=y;}struct ed {int to,nxt;
}t[mxn<<1];inline void add(int u,int v) {t[++cnt]=(ed) {v,hd[u]}; hd[u]=cnt;
}namespace lct {#define lc(u) (ch[u][0])#define rc(u) (ch[u][1])int fa[mxn],ch[mxn][2]; ll s[mxn],si[mxn],val[mxn];int isnotrt(int x) {return ch[fa[x]][0]==x||ch[fa[x]][1]==x;}void push_up(int x) {s[x]=s[lc(x)]+s[rc(x)]+val[x]+si[x];}void rotate(int x) {int y=fa[x],z=fa[y],tp=ch[y][1]==x;if(isnotrt(y)) ch[z][ch[z][1]==y]=x; fa[x]=z;ch[y][tp]=ch[x][tp^1]; fa[ch[x][tp^1]]=y;ch[x][tp^1]=y; fa[y]=x;push_up(y); push_up(x);}void splay(int x) {while(isnotrt(x)) {int y=fa[x],z=fa[y];if(isnotrt(y))(ch[y][1]==x)^(ch[z][1]==y)?rotate(x):rotate(y);rotate(x); }}ll cal(int x,ll tp,ll h) {if(rc(x)) return (tp-h)*2; else if(val[x]*2>tp) return (tp-val[x])*2; //重儿子只维护了子节点信息,当前节点需要特判else return tp-1;}void modify(int x,int w) {splay(x); ll tp=s[x]-s[lc(x)],h=s[rc(x)];ans-=cal(x,tp,h); s[x]+=w; val[x]+=w; tp+=w; if(h*2<tp+1) si[x]+=h,rc(x)=0; //只可能是总size变大,故只考虑重->轻ans+=cal(x,tp,h); push_up(x); int y=x; x=fa[x];for(;x;x=fa[y=x]) {splay(x); tp=s[x]-s[lc(x)],h=s[rc(x)];ans-=cal(x,tp,h); s[x]+=w,si[x]+=w,tp+=w;if(h*2<tp+1) si[x]+=h,rc(x)=0,h=0;if(s[y]*2>tp) si[x]-=s[y],rc(x)=y,h=s[y];ans+=cal(x,tp,h); push_up(x);}}void dfs(int u) {s[u]=val[u]; int son=0; ll mx=val[u];//这里一定要考虑自己for(int i=hd[u];i;i=t[i].nxt) {int v=t[i].to;if(v==fa[u]) continue ;fa[v]=u; dfs(v); s[u]+=s[v];if(s[v]>mx) mx=s[son=v];}ans+=min(s[u]-1,(s[u]-mx)*2);if(mx*2>=s[u]+1) rc(u)=son;si[u]=s[u]-val[u]-s[rc(u)];}
}
using namespace lct;int main()
{n=read(); m=read(); int u,v;for(int i=1;i<=n;++i) val[i]=read();for(int i=1;i<n;++i) {u=read(); v=read();add(u,v); add(v,u);}dfs(1); printf("%lld\n",ans);for(int i=1;i<=m;++i) {u=read(); v=read(); modify(u,v); printf("%lld\n",ans);}return 0;
}
