当前位置：首页 > news >正文

树链剖分+树状数组：ABC 460 G

news 2026/7/1 14:35:29

https://atcoder.jp/contests/abc460/tasks/abc460_g

考虑直接树剖

单点权重修改是容易的

单点颜色修改，往上更新是容易的，但往下合并不容易，把下方值往上传亦不容易

但如果往下合并的值提前记录好了呢？

我们可以多定义一个懒标记，代表这个点所有与它本身颜色不同子节点的值的和

利用这个懒标记，我们即可实现颜色翻转时子节点信息的向上传递。

这个懒标记的维护，只需要我们每次往上修改时，先修改完所有同颜色的，然后再修改第一个不同颜色的即可

#include<bits/stdc++.h>usingnamespacestd;#ifdefLOCAL#definedebug(...)fprintf(stdout,##__VA_ARGS__)#else#definedebug(...)void(0)#endif#defineintlonglonginlineintread(){intx=0,f=1;charch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}returnx*f;}#defineZ(x)(x)*(x)#definepbpush_back#definefifirst#definesesecond//#define M//#define mo#defineN300010intn,m,i,j,k,T;intc[N];inttot;vector<int>G[N];namespaceBin{intS[2][N];voidadd(intl,intr,intx,intco){autoAdd=[&](intx,intk,intco){if(!x)return;while(x<=tot){S[co][x]+=k;x+=x&-x;}};debug("ADD [%lld %lld] + %lld of (%lld)\n",l,r,x,co);Add(l,x,co);Add(r+1,-x,co);}intqry(intx,intco){intans=0;while(x){ans+=S[co][x];x-=x&-x;}returnans;}}namespaceBinC{intS[N];voidAdd(intx,intk){if(!x)return;// debug("BinCCCCCC %lld + %lld\n", x, k);while(x<=tot){S[x]+=k;x+=x&-x;}}intqry(intl,intr){autoQry=[&](intx)->int{intans=0;while(x){ans+=S[x];x-=x&-x;}returnans;};returnQry(r)-Qry(l-1);}boolcheck(intl,intr){intans=qry(l,r);// debug("Ans of [%lld %lld] is %lld\n", l, r, ans);if(ans==0||ans==r-l+1)returntrue;returnfalse;}}namespaceTree{intw[N],F[N],son[N],a[N],dfn[N];inttop[N];voiddfs1(intx,intfa){w[x]=1;F[x]=fa;for(inty:G[x])if(y!=fa){dfs1(y,x);w[x]+=w[y];if(!son[x]||w[y]>w[son[x]])son[x]=y;}}voiddfs2(intx,intfa){dfn[x]=++tot;a[tot]=x;if(son[x])top[son[x]]=top[x],dfs2(son[x],x);for(inty:G[x])if(y!=fa&&y!=son[x]){top[y]=y;dfs2(y,x);}// debug("top[%lld] = %lld\n", x, top[x]);}intFa(intx){if(!BinC::check(dfn[top[x]],dfn[x])){intl,r,mid;l=dfn[top[x]];r=dfn[x];while(l<r){mid=(l+r)>>1;if(BinC::check(mid,dfn[x]))r=mid;elsel=mid+1;}returna[l];}if(c[F[top[x]]]==c[x])returnFa(F[top[x]]);elsereturntop[x];}voidadd(intx,intk,intcol){debug("Tree add %lld [%lld] %lld\n",x,k,col);if(c[x]!=col)return;if(!BinC::check(dfn[top[x]],dfn[x])){intl,r,mid;l=mid=dfn[top[x]];r=dfn[x];while(l<r){mid=(l+r)>>1;if(BinC::check(mid,dfn[x]))r=mid;elsel=mid+1;}// debug("Now [%lld %lld] %lld %lld\n", dfn[top[x]], dfn[x], mid, (int)BinC :: check(mid, dfn[x]));Bin::add(l,dfn[x],k,col);Bin::add(l-1,l-1,k,col);}else{Bin::add(dfn[top[x]],dfn[x],k,col);if(c[F[top[x]]]==c[x])add(F[top[x]],k,col);elseBin::add(dfn[F[top[x]]],dfn[F[top[x]]],k,col);}}voidop2(intx,intk){debug("OP2 %lld(%lld) += %lld\n",x,Fa(x),k);add(x,k,c[x]);Bin::add(dfn[x],dfn[x],k,1-c[x]);}intop3(intx){intpare=Fa(x);debug("OP3 %lld : %lld == %lld\n",x,pare,Bin::qry(dfn[pare],c[x]));returnBin::qry(dfn[pare],c[x]);}voidop1(intx){intk=Bin::qry(dfn[x],c[x]);if(c[F[x]]==c[x])add(F[x],-k,c[x]);elseBin::add(dfn[F[x]],dfn[F[x]],-k,c[x]);BinC::Add(dfn[x],-c[x]+(1-c[x]));c[x]=1-c[x];k=Bin::qry(dfn[x],c[x]);if(c[F[x]]==c[x])add(F[x],k,c[x]);elseBin::add(dfn[F[x]],dfn[F[x]],k,c[x]);}}signedmain(){#ifdefLOCALfreopen("in.txt","r",stdin);freopen("out.txt","w",stdout);#endif// srand(time(NULL));// T = read();// while(T--) {//// }intq,u,v;n=read();q=read();vector<int>w(n+10);for(i=1;i<=n;++i)w[i]=read();for(i=1;i<=n;++i)c[i]=read();c[0]=n<<2;G[0].pb(1);for(i=1;i<n;++i){u=read();v=read();G[u].pb(v);G[v].pb(u);}Tree::dfs1(0,0);Tree::dfs2(0,0);// for(i = 1; i <= tot; ++i) debug("%lld ", Tree :: a[i]); debug("\n");for(i=0;i<=n;++i)BinC::Add(Tree::dfn[i],c[i]);for(i=1;i<=n;++i)Tree::op2(i,w[i]);while(q--){intop,x;op=read();x=read();if(op==1)Tree::op1(x);if(op==2){k=read();Tree::op2(x,k);}if(op==3){printf("%lld\n",Tree::op3(x));}for(i=1;i<=n;++i)debug("%lld ",Bin::qry(Tree::dfn[i],0));debug("\n");for(i=1;i<=n;++i)debug("%lld ",Bin::qry(Tree::dfn[i],1));debug("\n");debug("-------------------------------\n");}return0;}