https://atcoder.jp/contests/abc460/tasks/abc460_g考虑直接树剖单点权重修改是容易的单点颜色修改往上更新是容易的但往下合并不容易把下方值往上传亦不容易但如果往下合并的值提前记录好了呢我们可以多定义一个懒标记代表这个点所有与它本身颜色不同子节点的值的和利用这个懒标记我们即可实现颜色翻转时子节点信息的向上传递。这个懒标记的维护只需要我们每次往上修改时先修改完所有同颜色的然后再修改第一个不同颜色的即可#includebits/stdc.husingnamespacestd;#ifdefLOCAL#definedebug(...)fprintf(stdout,##__VA_ARGS__)#else#definedebug(...)void(0)#endif#defineintlonglonginlineintread(){intx0,f1;charchgetchar();while(ch0||ch9){if(ch-)f-1;chgetchar();}while(ch0ch9){x(x1)(x3)(ch^48);chgetchar();}returnx*f;}#defineZ(x)(x)*(x)#definepbpush_back#definefifirst#definesesecond//#define M//#define mo#defineN300010intn,m,i,j,k,T;intc[N];inttot;vectorintG[N];namespaceBin{intS[2][N];voidadd(intl,intr,intx,intco){autoAdd[](intx,intk,intco){if(!x)return;while(xtot){S[co][x]k;xx-x;}};debug(ADD [%lld %lld] %lld of (%lld)\n,l,r,x,co);Add(l,x,co);Add(r1,-x,co);}intqry(intx,intco){intans0;while(x){ansS[co][x];x-x-x;}returnans;}}namespaceBinC{intS[N];voidAdd(intx,intk){if(!x)return;// debug(BinCCCCCC %lld %lld\n, x, k);while(xtot){S[x]k;xx-x;}}intqry(intl,intr){autoQry[](intx)-int{intans0;while(x){ansS[x];x-x-x;}returnans;};returnQry(r)-Qry(l-1);}boolcheck(intl,intr){intansqry(l,r);// debug(Ans of [%lld %lld] is %lld\n, l, r, ans);if(ans0||ansr-l1)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!fay!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;ldfn[top[x]];rdfn[x];while(lr){mid(lr)1;if(BinC::check(mid,dfn[x]))rmid;elselmid1;}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;lmiddfn[top[x]];rdfn[x];while(lr){mid(lr)1;if(BinC::check(mid,dfn[x]))rmid;elselmid1;}// 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){intpareFa(x);debug(OP3 %lld : %lld %lld\n,x,pare,Bin::qry(dfn[pare],c[x]));returnBin::qry(dfn[pare],c[x]);}voidop1(intx){intkBin::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];kBin::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;nread();qread();vectorintw(n10);for(i1;in;i)w[i]read();for(i1;in;i)c[i]read();c[0]n2;G[0].pb(1);for(i1;in;i){uread();vread();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(i0;in;i)BinC::Add(Tree::dfn[i],c[i]);for(i1;in;i)Tree::op2(i,w[i]);while(q--){intop,x;opread();xread();if(op1)Tree::op1(x);if(op2){kread();Tree::op2(x,k);}if(op3){printf(%lld\n,Tree::op3(x));}for(i1;in;i)debug(%lld ,Bin::qry(Tree::dfn[i],0));debug(\n);for(i1;in;i)debug(%lld ,Bin::qry(Tree::dfn[i],1));debug(\n);debug(-------------------------------\n);}return0;}
