「ZJOI2011」道馆之战
给定一棵树，每一个节点 \(2\) 个房间，可以为薄冰或者障碍物，给定两个操作：修改某一个房间的两个区域，查询从 \(u\) 走到 \(v\) 最短可以经过多少薄冰（最终可以不到达 \(v\)）。
毫无疑问，维护树上信息，肯定是需要重链剖分的，对于线段树上每一个区间 \([l,r]\)，我们需要维护一下信息（其中 \(0 \le i,j \le 1\)）。
\(lmax_i\)：表示从 \(l\) 的 \(i\) 房间出发向 \(r\) 出发最多能经过多少薄冰（注意最终可以不用到达 \(r\)，并且最多走到 \(r\)）。
\(rmax_i\)：表示从 \(r\) 的 \(i\) 房间出发向 \(r\) 出发最多能经过多少薄冰（同样最终可以不用到达 \(l\)，并且最多走到 \(l\)）。
\(dis_{i,j}\)：表示从 \(l\) 的 \(i\) 房间走到 \(r\) 的 \(j\) 房间最多能经过多少薄冰（这次是必须到达）。
那么我们就可以如下代码将两个相邻区间合并为一个区间了。
for(int i=0;i<=1;i++){
for(int j=0;j<=1;j++){
c.lmax[i]=max(c.lmax[i],max(a.lmax[i],a.dis[i][j]+b.lmax[j]));
c.rmax[i]=max(c.rmax[i],max(b.rmax[i],b.dis[j][i]+a.rmax[j]));
for(int k=0;k<=1;k++) c.dis[i][j]=max(-INF,c.dis[i][j],a.dis[i][k]+b.dis[k][j]);
}
}
但是对于最后对于树剖查询合并两条链子时，我们需要的是：
但由于是树剖向上跳从而求得答案，所以实际的应该是：
所以我们应该这样将左边的链旋转（因为具有对称性，所以不是全部旋转）：
swap(res.lmax[0],res.rmax[0]);
swap(res.lmax[1],res.rmax[1]);
swap(res.dis[1][0],res.dis[0][1]);
这里再解释一下为什么会这样设计线段树所记录的信息：
对于 \(lmax_i\) 很明显是用来记录答案，又因为我们最后需要旋转，方向不确定，所以需要记录 \(rmax_i\)，对于 \(dis_{i,j}\) 我们需要用来合并答案。但是可能会有人认为 \(dis_{i,j}\) 没用，但是因为题目中的“最终可以不到达 \(v\)”，所以会存在错误合并，例如下图：
红色路径为 \(dis_{0,0}\) 的答案路径，蓝色路径为 \(lmax_0\) 的路径。
#include<bits/stdc++.h>
using namespace std;
int n,m,x,y,tot,siz[50001],fa[50001],top[50001],son[50001],dep[50001],dfn[50001];
vector <int> G[50001];
char s[10];
void dfs1(int rt){
son[rt]=-1;
siz[rt]=1;
for(int i=0;i<G[rt].size();i++){
int to=G[rt][i];
if(!dep[to]){
dep[to]=dep[rt]+1;
fa[to]=rt;
dfs1(to);
siz[rt]+=siz[to];
if(son[rt]==-1||siz[to]>siz[son[rt]]) son[rt]=to;
}
}
}
void dfs2(int rt,int t){
top[rt]=t;
dfn[rt]=++tot;
if(son[rt]==-1) return;
dfs2(son[rt],t);
for(int i=0;i<G[rt].size();i++){
int to=G[rt][i];
if(to!=son[rt]&&to!=fa[rt]) dfs2(to,to);
}
}
struct node{
int lmax[3],rmax[3],dis[3][3];
node(){
memset(lmax,0,sizeof(lmax));
memset(rmax,0,sizeof(rmax));
memset(dis,0,sizeof(dis));
}
bool empty(){
if(!lmax[0]&&!lmax[1]&&!rmax[0]&&!rmax[1]&&!dis[0][0]&&!dis[0][1]&&!dis[1][0]&&!dis[1][1]) return true;
else return false;
}
}t[200001];
node merge(node a,node b){
node c;
if(a.empty()) return b;
if(b.empty()) return a;
for(int i=0;i<=1;i++){
for(int j=0;j<=1;j++){
c.lmax[i]=max(c.lmax[i],max(a.lmax[i],a.dis[i][j]+b.lmax[j]));
c.rmax[i]=max(c.rmax[i],max(b.rmax[i],b.dis[j][i]+a.rmax[j]));
c.dis[i][j]=-1e8;
for(int k=0;k<=1;k++) c.dis[i][j]=max(c.dis[i][j],a.dis[i][k]+b.dis[k][j]);
}
}
return c;
}
void updata(int rt,int l,int r,int x,int v1,int v2){
if(l==r){
if(v1==1&&v2==1){
t[rt].lmax[0]=t[rt].lmax[1]=t[rt].rmax[0]=t[rt].rmax[1]=t[rt].dis[0][1]=t[rt].dis[1][0]=2;
t[rt].dis[0][0]=t[rt].dis[1][1]=1;
}
else if(v1==1&&v2==0){
t[rt].lmax[0]=t[rt].rmax[0]=t[rt].dis[0][0]=1;
t[rt].lmax[1]=t[rt].rmax[1]=0;
t[rt].dis[1][1]=t[rt].dis[1][0]=t[rt].dis[0][1]=-1e8;
}
else if(v1==0&&v2==1){
t[rt].lmax[1]=t[rt].rmax[1]=t[rt].dis[1][1]=1;
t[rt].lmax[0]=t[rt].rmax[0]=0;
t[rt].dis[0][0]=t[rt].dis[1][0]=t[rt].dis[0][1]=-1e8;
}
else{
t[rt].lmax[0]=t[rt].lmax[1]=t[rt].rmax[0]=t[rt].rmax[1]=0;
t[rt].dis[0][0]=t[rt].dis[0][1]=t[rt].dis[1][0]=t[rt].dis[1][1]=-1e8;
}
return;
}
int mid=(l+r)/2;
if(x<=mid) updata(rt*2,l,mid,x,v1,v2);
else updata(rt*2+1,mid+1,r,x,v1,v2);
t[rt]=merge(t[rt*2],t[rt*2+1]);
}
node query(int rt,int l,int r,int L,int R){
if(L<=l&&r<=R) return t[rt];
int mid=(l+r)/2;
node res;
if(L<=mid) res=merge(res,query(rt*2,l,mid,L,R));
if(R>mid) res=merge(res,query(rt*2+1,mid+1,r,L,R));
return res;
}
int lookup(int u,int v){
node r1,r2;
while(top[u]!=top[v]){
if(dep[top[u]]>dep[top[v]]){
r1=merge(query(1,1,n,dfn[top[u]],dfn[u]),r1);
u=fa[top[u]];
}
else{
r2=merge(query(1,1,n,dfn[top[v]],dfn[v]),r2);
v=fa[top[v]];
}
}
if(dfn[u]>dfn[v]) r1=merge(query(1,1,n,dfn[v],dfn[u]),r1);
else r2=merge(query(1,1,n,dfn[u],dfn[v]),r2);
swap(r1.lmax[0],r1.rmax[0]);
swap(r1.lmax[1],r1.rmax[1]);
swap(r1.dis[1][0],r1.dis[0][1]);
r1=merge(r1,r2);
return max(r1.lmax[0],r1.lmax[1]);
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<n;i++){
scanf("%d%d",&x,&y);
G[x].push_back(y);
G[y].push_back(x);
}
dep[1]=1;
dfs1(1);
dfs2(1,1);
for(int i=1;i<=n;i++){
scanf("%s",s);
updata(1,1,n,dfn[i],(s[0]=='.'),(s[1]=='.'));
}
while(m--){
scanf("%s%d",s,&x);
if(s[0]=='Q'){
scanf("%d",&y);
printf("%d\n",lookup(x,y));
}
else{
scanf("%s",s);
updata(1,1,n,dfn[x],(s[0]=='.'),(s[1]=='.'));
}
}
return 0;
}