给定一棵树,定义每个点的操作为把这个点到1号点的路径覆盖上颜色i,每次该点到1号点经过的不同颜色段数会加到答案中,要使所有点按某一顺序操作完后答案最大
给定每个点要执行的操作次数,并给出m次修改,问每次修改后的最大答案
\(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; }