洛谷题目页面传送门
有一棵树(T=(V,E),|V|=n,|E|=n-1)。节点(i)有(2)个房间，每个房间是薄冰或障碍物，分别用(a_{i,1},a_{i,2})表示（( exttt.)表示薄冰，( exttt#)表示障碍物）。你需要支持以下(2)种(q)次操作：
- ( exttt C x y)：(y)是一个长度为(2)的字符串，表示将节点(x)的房间改成(y)；
- ( exttt Q x y)：查询从节点(x)往节点(y)走最多能踏过多少个薄冰。可以从节点(x)的任意房间出发。每次可以移到同节点的另一房间或往(y)方向的下一个节点的同一房间。障碍物不能走。走过的房间不能走。最终不必到达(y)。
(ninleft[1,5 imes10^4 ight],qinleft[1,10^5 ight])。
一眼的重剖。
先来考虑若出在线性结构上该怎么做。单点修改，区间查询，BIT又太逊，考虑线段树。每个节点维护一大堆东西，然后一脸区间可合并的样子。对于每个线段树节点(i)，设表示([l_i,r_i])，那么最终要求的“最多能踏过多少个薄冰”显然是必须要记录的，设为(mx_i)。又由于区间没有方向，但是操作( exttt Q)中的(x,y)左右关系不确定，所以要记录从左往右、从右往左(2)种方向上的答案(mxl_i,mxr_i)。
接下来考虑合并。以从左往右为例。([l_i,r_i])的答案显然分为(2)种情况：轨迹在([l_i,r_{lson_i}])内和跨越它。情况(1)显然是(mxl_{lson_i})就够了的。情况(2)则需要前提条件——([l_i,r_{lson_i}])能够走通。于是需要再维护一个(can_i)（这个(2)种方向是可以互用的）。又由于在(r_{lson_i},l_{rson_i})处的接口成功性与连接的房间（(1)还是(2)）有关，所以我们每个记录的东西都要分起点终点四种情况（即(mxl_{i,0/1,0/1},mxr_{i,0/1,0/1},can_{i,0/1,0/1})）。此时可合并性已经很显然了。
由于这个线段树节点合并的方法有点复杂，记录的(12)个量互相依存，于是查询函数之类直接返回节点结构体。
现在来考虑树上的情况。考虑重剖，由于这个线段树节点是分方向的，于是不能像普通算和、(min/max)之类直接将一个个剖出来的重链的结果累计到路径的总结果中，需要维护(x omathrm{LCA}(x,y),y omathrm{LCA}(x,y))这(2)条直链的总结果（都是线段树节点结构体）。最终将这(2)条直链的总结果合并时，要注意将(x omathrm{LCA}(x,y))的总结果方向翻转（因为根据重剖的性质，方向是从上往下的，而我们从(x)往(mathrm{LCA}(x,y))走，理应是从下往上的）。
线性结构上的线段树复杂度单(log)，加了个重剖变成(mathrm O!left(qlog^2n ight))。
对了有个要注意的地方，就是线段树空节点与非空节点合并时要特判，不然会WA到自闭，已加入sb错误列表（第(2)条）（
代码：
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
const int N=50000;
int n,qu;
vector<int> nei[N+1];//邻接表
char a[N+1][5];//房间情况
int fa[N+1],dep[N+1],sz[N+1],wson[N+1],top[N+1],dfn[N+1],nowdfn,mng[N+1];//重剖
void dfs1(int x=1){//重剖
sz[x]=1;
for(int i=0;i<nei[x].size();i++){
int y=nei[x][i];
if(y==fa[x])continue;
fa[y]=x;
dep[y]=dep[x]+1;
dfs1(y);
sz[x]+=sz[y];
if(sz[y]>sz[wson[x]])wson[x]=y;
}
}
void dfs2(int x=1,int t=1){//重剖
mng[dfn[x]=++nowdfn]=x;
top[x]=t;
if(wson[x])dfs2(wson[x],t);
for(int i=0;i<nei[x].size();i++){
int y=nei[x][i];
if(y!=fa[x]&&y!=wson[x])dfs2(y,y);
}
}
struct segtree{//线段树
struct node{//节点
int l,r,mxl[2][2],mxr[2][2];bool can[2][2];
node(){l=0;}//空节点的标志
node rev(){//方向翻转
node res=*this;
swap(res.mxl[0][0],res.mxr[0][0]);
swap(res.mxl[0][1],res.mxr[0][1]);
swap(res.mxl[1][0],res.mxr[1][0]);
swap(res.mxl[1][1],res.mxr[1][1]);
swap(res.can[0][1],res.can[1][0]);
return res;
}
void prt(){//调试用
printf("nd[%d,%d]=
",l,r);
printf(" mxl[0][0]=%d mxl[0][1]=%d mxl[1][0]=%d mxl[1][1]=%d
",mxl[0][0],mxl[0][1],mxl[1][0],mxl[1][1]);
printf(" mxr[0][0]=%d mxr[0][1]=%d mxr[1][0]=%d mxr[1][1]=%d
",mxr[0][0],mxr[0][1],mxr[1][0],mxr[1][1]);
printf(" can[0][0]=%d can[0][1]=%d can[1][0]=%d can[1][1]=%d
",can[0][0],can[0][1],can[1][0],can[1][1]);
}
}nd[N<<2];
#define l(p) nd[p].l
#define r(p) nd[p].r
#define mxl(p) nd[p].mxl
#define mxr(p) nd[p].mxr
#define can(p) nd[p].can
void sprup(node &p,node lson,node rson){//上传（即合并）
if(!lson.l)return p=rson,void();
if(!rson.l)return p=lson,void();
p.l=lson.l;p.r=rson.r;
p.mxl[0][0]=max(lson.mxl[0][0]+lson.can[0][0]*rson.mxl[0][0],lson.mxl[0][1]+lson.can[0][1]*rson.mxl[1][0]);
p.mxl[0][1]=max(lson.mxl[0][0]+lson.can[0][0]*rson.mxl[0][1],lson.mxl[0][1]+lson.can[0][1]*rson.mxl[1][1]);
p.mxl[1][0]=max(lson.mxl[1][0]+lson.can[1][0]*rson.mxl[0][0],lson.mxl[1][1]+lson.can[1][1]*rson.mxl[1][0]);
p.mxl[1][1]=max(lson.mxl[1][0]+lson.can[1][0]*rson.mxl[0][1],lson.mxl[1][1]+lson.can[1][1]*rson.mxl[1][1]);
p.mxr[0][0]=max(rson.mxr[0][0]+rson.can[0][0]*lson.mxr[0][0],rson.mxr[0][1]+rson.can[1][0]*lson.mxr[1][0]);
p.mxr[0][1]=max(rson.mxr[0][0]+rson.can[0][0]*lson.mxr[0][1],rson.mxr[0][1]+rson.can[1][0]*lson.mxr[1][1]);
p.mxr[1][0]=max(rson.mxr[1][0]+rson.can[0][1]*lson.mxr[0][0],rson.mxr[1][1]+rson.can[1][1]*lson.mxr[1][0]);
p.mxr[1][1]=max(rson.mxr[1][0]+rson.can[0][1]*lson.mxr[0][1],rson.mxr[1][1]+rson.can[1][1]*lson.mxr[1][1]);
p.can[0][0]=lson.can[0][0]&&rson.can[0][0]||lson.can[0][1]&&rson.can[1][0];
p.can[0][1]=lson.can[0][0]&&rson.can[0][1]||lson.can[0][1]&&rson.can[1][1];
p.can[1][0]=lson.can[1][0]&&rson.can[0][0]||lson.can[1][1]&&rson.can[1][0];
p.can[1][1]=lson.can[1][0]&&rson.can[0][1]||lson.can[1][1]&&rson.can[1][1];
}
void sprup(int p){sprup(nd[p],nd[p<<1],nd[p<<1|1]);}//真正的上传
void bld(int l=1,int r=n,int p=1){//建树
l(p)=l;r(p)=r;
if(l==r){//区间大小为1时的处理
mxl(p)[0][0]=mxr(p)[0][0]=a[mng[l]][0]=='.';
mxl(p)[0][1]=mxr(p)[0][1]=a[mng[l]][0]=='.'?a[mng[l]][1]=='.'?2:1:0;
mxl(p)[1][0]=mxr(p)[1][0]=a[mng[l]][1]=='.'?a[mng[l]][0]=='.'?2:1:0;
mxl(p)[1][1]=mxr(p)[1][1]=a[mng[l]][1]=='.';
can(p)[0][0]=a[mng[l]][0]=='.';
can(p)[0][1]=can(p)[1][0]=a[mng[l]][0]=='.'&&a[mng[l]][1]=='.';
can(p)[1][1]=a[mng[l]][1]=='.';
return;
}
int mid=l+r>>1;
bld(l,mid,p<<1);bld(mid+1,r,p<<1|1);
sprup(p);
}
void init(){bld();}
node mx(int l,int r,int p=1){//区间查询
if(l<=l(p)&&r>=r(p))return /*nd[p].prt(),*/nd[p];
int mid=l(p)+r(p)>>1;
node res;
if(l<=mid)sprup(res,res,mx(l,r,p<<1));
if(r>mid)sprup(res,res,mx(l,r,p<<1|1));
// res.prt();
return res;
}
void chg(int x,char v[],int p=1){//单点修改
if(l(p)==r(p)){
mxl(p)[0][0]=mxr(p)[0][0]=v[0]=='.';
mxl(p)[0][1]=mxr(p)[0][1]=v[0]=='.'?v[1]=='.'?2:1:0;
mxl(p)[1][0]=mxr(p)[1][0]=v[1]=='.'?v[0]=='.'?2:1:0;
mxl(p)[1][1]=mxr(p)[1][1]=v[1]=='.';
can(p)[0][0]=v[0]=='.';
can(p)[0][1]=can(p)[1][0]=v[0]=='.'&&v[1]=='.';
can(p)[1][1]=v[1]=='.';
return;
}
int mid=l(p)+r(p)>>1;
chg(x,v,p<<1|(x>mid));
sprup(p);
}
}segt;
int mx(int x,int y){//树上链查询
segtree::node res[2];//2条直链的总结果
bool now=0;//当前在合并到哪条直链
while(top[x]!=top[y]){
if(dep[top[x]]<dep[top[y]])now^=1,swap(x,y);//改变当前状态
segt.sprup(res[now],segt.mx(dfn[top[x]],dfn[x]),res[now]);//合并当前重链的结果到所在直链的总结果
x=fa[top[x]];
}
if(dep[x]<dep[y])now^=1,swap(x,y);//改变当前状态
segt.sprup(res[now],segt.mx(dfn[y],dfn[x]),res[now]);//合并当前重链的结果到所在直链的总结果
// res[0].rev().prt();res[1].prt();
segt.sprup(res[0],res[0].rev()/*左直链要左右翻转*/,res[1]);//2条直链合并
return max(max(res[0].mxl[0][0],res[0].mxl[0][1]),max(res[0].mxl[1][0],res[0].mxl[1][1]));//最终答案
}
int main(){
cin>>n>>qu;
for(int i=1;i<n;i++){
int x,y;
cin>>x>>y;
nei[x].pb(y);nei[y].pb(x);
}
for(int i=1;i<=n;i++)cin>>a[i];
dfs1();dfs2();//重剖
segt.init();//线段树初始化
while(qu--){
char tp,z[5];int x,y;
cin>>tp>>x;
if(tp=='Q')cin>>y,cout<<mx(x,y)<<"
";
else cin>>z,segt.chg(dfn[x],z);
}
return 0;
}
```cpp