看了半天题解代码大概明白他在干啥了。写篇题解总结一下。
题面：一棵树，每个点黑色或白色，有权值。五个操作：
- 改变一个点颜色。
- 使点 \(x\) 所在的同色连通块权值加 \(val\)。
- 查询 \(x\) 同色连通块最大值。
- 链 \((x,y)\) 权值加 \(val\)。
- \(x\) 子树加 \(val\)。
首先我们看到 \(4,5\) 两个操作知道这是个树剖。然后我们得考虑怎么在树剖的一棵线段树上把颜色一起维护上。
树剖以后连通块就变成了一堆链，也就是一大堆连续段。显然不可能一个一个修改，原地爆炸。那么考虑在下传的时候搞点事情。
具体的，我们可以把每个节点的子树在 dfs 序上代表的区间在线段树上插入，来标明这个区间是什么颜色的。然后进行和颜色有关的操作的时候就看一下这个区间是什么颜色，如果颜色不同直接返回。这个区间可以每个线段树节点上个 set 维护。
这样就相对比较好搞了，来看前三个操作：
改变颜色，把这个节点代表的区间删除，反转颜色和信息，然后再把区间加进去。
连通块加，找到连通块的根节点（就是最上边的那个节点，这个节点的子树能覆盖整个连通块），然后直接更新，注意颜色。
查询连通块，和连通块加差不多。
思路只要捋明白其实很显明，但是码量巨大。
（实际上我觉得还不如直接看代码更好理解）
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <set>
#include <vector>
#define lson rt<<1
#define rson rt<<1|1
using namespace std;
const int inf=2147483647;
int n,m;
struct node{
int v,next;
}edge[400010];
int t,head[200010];
void add(int u,int v){
edge[++t].v=v;edge[t].next=head[u];head[u]=t;
}
int num,dfn[200010],rk[200010],fa[200010],dep[200010],size[200010],son[200010],Fa[200010][21];
int L[200010],R[200010],col[200010],val[200010];
//树剖
void dfs1(int x,int f){
dep[x]=dep[f]+1;size[x]=1;fa[x]=Fa[x][0]=f;
for(int i=1;i<=__lg(n);i++)Fa[x][i]=Fa[Fa[x][i-1]][i-1];
for(int i=head[x];i;i=edge[i].next){
if(edge[i].v!=f){
dfs1(edge[i].v,x);
size[x]+=size[edge[i].v];
if(size[edge[i].v]>size[son[x]])son[x]=edge[i].v;
}
}
}
void dfs2(int x,int f,int tp){
dfn[x]=++num;L[x]=tp;rk[num]=x;
if(son[x])dfs2(son[x],x,tp);
for(int i=head[x];i;i=edge[i].next){
if(edge[i].v!=son[x]&&edge[i].v!=f)dfs2(edge[i].v,x,edge[i].v);
}
R[x]=num;
}
//线段树
struct tr{
set<int>b,w;//黑白区间
int valw,valb,lz,lzb,lzw;//分别存储黑色和白色的信息
bool covw,covb;//区间所有点是否全都是黑色/白色
}tree[800010];
void pushtag(int rt,int val){
tree[rt].valw+=val;tree[rt].valb+=val;tree[rt].lz+=val;
}
void pushup(int rt){
tree[rt].valw=tree[rt].valb=-inf;
if(tree[lson].b.empty())tree[rt].valw=max(tree[rt].valw,tree[lson].valw);
if(tree[rson].b.empty())tree[rt].valw=max(tree[rt].valw,tree[rson].valw);
if(tree[lson].w.empty())tree[rt].valb=max(tree[rt].valb,tree[lson].valb);
if(tree[rson].w.empty())tree[rt].valb=max(tree[rt].valb,tree[rson].valb);
tree[rt].covb=tree[lson].covb&&tree[rson].covb;
tree[rt].covw=tree[lson].covw&&tree[rson].covw;
}
//检查tree[rt]的线段树区间是否有颜色col
bool check(int rt,int l,int r,int col){
set<int>::iterator it=(col?tree[rt].b:tree[rt].w).lower_bound(l);
if(it==(col?tree[rt].b:tree[rt].w).end())return false;
return (*it)<=r;
}
void pushdown(int rt){
if(tree[rt].lz){
pushtag(lson,tree[rt].lz);pushtag(rson,tree[rt].lz);
tree[rt].lz=0;
}
if(tree[rt].lzb){
if(tree[lson].w.empty()){
tree[lson].valb+=tree[rt].lzb;tree[lson].lzb+=tree[rt].lzb;
}
if(tree[rson].w.empty()){
tree[rson].valb+=tree[rt].lzb;tree[rson].lzb+=tree[rt].lzb;
}
tree[rt].lzb=0;
}
if(tree[rt].lzw){
if(tree[lson].b.empty()){
tree[lson].valw+=tree[rt].lzw;tree[lson].lzw+=tree[rt].lzw;
}
if(tree[rson].b.empty()){
tree[rson].valw+=tree[rt].lzw;tree[rson].lzw+=tree[rt].lzw;
}
tree[rt].lzw=0;
}
}
void build(int rt,int l,int r){
if(l==r){
if(col[rk[l]]){
tree[rt].valb=val[rk[l]];tree[rt].valw=-inf;tree[rt].covb=true;
}
else{
tree[rt].valw=val[rk[l]];tree[rt].valb=-inf;tree[rt].covw=true;
}
return;
}
int mid=(l+r)>>1;
build(lson,l,mid);build(rson,mid+1,r);
pushup(rt);
}
//反转颜色信息
void update(int rt,int l,int r,int pos){
if(l==r){
swap(tree[rt].valb,tree[rt].valw);
swap(tree[rt].covb,tree[rt].covw);
return;
}
pushdown(rt);
int mid=(l+r)>>1;
if(pos<=mid)update(lson,l,mid,pos);
else update(rson,mid+1,r,pos);
pushup(rt);
}
//插入删除区间
void ins(int rt,int L,int R,int l,int r,int k,int p){
if(l<=L&&R<=r){
(p?tree[rt].b:tree[rt].w).insert(k);return;
}
pushdown(rt);
int mid=(L+R)>>1;
if(l<=mid)ins(lson,L,mid,l,r,k,p);
if(mid<r)ins(rson,mid+1,R,l,r,k,p);
pushup(rt);
}
void del(int rt,int L,int R,int l,int r,int k,int p){
if(l<=L&&R<=r){
(p?tree[rt].b:tree[rt].w).erase(k);return;
}
pushdown(rt);
int mid=(L+R)>>1;
if(l<=mid)del(lson,L,mid,l,r,k,p);
if(mid<r)del(rson,mid+1,R,l,r,k,p);
pushup(rt);
}
//45操作的update
void modi(int rt,int L,int R,int l,int r,int w){
if(l<=L&&R<=r){
pushtag(rt,w);return;
}
pushdown(rt);
int mid=(L+R)>>1;
if(l<=mid)modi(lson,L,mid,l,r,w);
if(mid<r)modi(rson,mid+1,R,l,r,w);
pushup(rt);
}
//修改某个颜色块
void Modi(int rt,int L,int R,int l,int r,int w,int p){
if(check(rt,l,r,p^1))return;//如果当前段有相反颜色则直接返回
if(l<=L&&R<=r){
if(p)tree[rt].valb+=w,tree[rt].lzb+=w;
else tree[rt].valw+=w,tree[rt].lzw+=w;
return;
}
pushdown(rt);
int mid=(L+R)>>1;
if(l<=mid)Modi(lson,L,mid,l,r,w,p);
if(mid<r)Modi(rson,mid+1,R,l,r,w,p);
pushup(rt);
}
//查询颜色块 和上边差不多
int query(int rt,int L,int R,int l,int r,int p){
if(check(rt,l,r,p^1))return 0;
if(l<=L&&R<=r)return p?tree[rt].valb:tree[rt].valw;
pushdown(rt);
int mid=(L+R)>>1,val=0;
if(l<=mid)val=max(val,query(lson,L,mid,l,r,p));
if(mid<r)val=max(val,query(rson,mid+1,R,l,r,p));
return val;
}
//找一条链最右边颜色为p的点的dfs序
int ask(int rt,int L,int R,int l,int r,int p){
if(p?tree[rt].covb:tree[rt].covw)return 0;
if(p?tree[rt].covw:tree[rt].covb)return min(r,R);
if(L==R)return L;
pushdown(rt);
int mid=(L+R)>>1;
if(mid<r){
int tmp=ask(rson,mid+1,R,l,r,p);
if(tmp)return tmp;
}
if(l<=mid)return ask(lson,L,mid,l,r,p);
return 0;
}
//找x所在的连通块的根节点
int findfa(int x,int dep){
for(int i=0;i<=__lg(n);i++){
if((dep>>i)&1)x=Fa[x][i];
}
return x;
}
int chainfind(int x){
int y=x,c=col[x];
while(x){
int tmp=ask(1,1,n,dfn[L[x]],dfn[x],c);
if(tmp)return findfa(y,dep[y]-dep[rk[tmp]]-1);
x=fa[L[x]];
}
return 1;
}
//4操作
void chainupdate(int x,int y,int val){
while(L[x]!=L[y]){
if(dep[L[x]]<dep[L[y]])swap(x,y);
modi(1,1,n,dfn[L[x]],dfn[x],val);
x=fa[L[x]];
}
if(dep[x]>dep[y])swap(x,y);
modi(1,1,n,dfn[x],dfn[y],val);
}
int main(){
freopen("astill.in","r",stdin);
freopen("astill.out","w",stdout);
scanf("%d%d",&n,&m);
for(int i=1;i<n;i++){
int u,v;scanf("%d%d",&u,&v);
add(u,v);add(v,u);
}
dfs1(1,0);dfs2(1,0,1);
for(int i=1;i<=n;i++)scanf("%d",&col[i]);
for(int i=1;i<=n;i++)scanf("%d",&val[i]);
for(int i=1;i<=n;i++)ins(1,1,n,dfn[i],R[i],dfn[i],col[i]);
build(1,1,n);
for(int i=1;i<=m;i++){
int od,x,y,w;scanf("%d%d",&od,&x);
if(od==1){
del(1,1,n,dfn[x],R[x],dfn[x],col[x]);
col[x]^=1;
ins(1,1,n,dfn[x],R[x],dfn[x],col[x]);
update(1,1,n,dfn[x]);
}
else if(od==2){
scanf("%d",&w);
x=chainfind(x);
Modi(1,1,n,dfn[x],R[x],w,col[x]);
}
else if(od==3){
x=chainfind(x);
printf("%d\n",query(1,1,n,dfn[x],R[x],col[x]));
}
else if(od==4){
scanf("%d%d",&y,&w);
chainupdate(x,y,w);
}
else{
scanf("%d",&w);
modi(1,1,n,dfn[x],R[x],w);
}
}
return 0;
}