LCT 线段树
BZOJ题目传送门
洛谷题目传送门
码力不行啊
操作1就是access啦
操作2就是
w[x]+w[y]−2∗w[lca(x,y)]+1
w
[
x
]
+
w
[
y
]
−
2
∗
w
[
l
c
a
(
x
,
y
)
]
+
1
啦
操作3就是先DFS序然后线段树查一查区间最大值啦
每个节点到根的颜色数为虚边数+1。（access后虚边即代表和上一个点的颜色不一样）
代码：
#include<cctype>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define N 100005
#define F inline
#define V F void
using namespace std;
struct LCT{ int to[2],fa,f,p; }t[N];
struct tree{ int l,r,mx,tg; }s[N<<2];
struct edge{ int next,to; }ed[N<<2];
int n,m,ti,i,k,h[N],c[N],L[N],R[N],fa[N][18],dep[N],id[N];
F char readc(){
static char buf[100000],*l=buf,*r=buf;
if (l==r) r=(l=buf)+fread(buf,1,100000,stdin);
if (l==r) return EOF; return *l++;
}
F int _read(){
int x=0; char ch=readc();
while (!isdigit(ch)) ch=readc();
while (isdigit(ch)) x=(x<<3)+(x<<1)+(ch^48),ch=readc();
return x;
}
V writec(int x){ if (x>9) writec(x/10); putchar(x%10+48); }
V _write(int x){ writec(x),putchar('\n'); }
//以上为IO优化
void dfs(int x,int dth){
dep[x]=dth,id[L[x]=++ti]=x;
for (int i=h[x],v;i;i=ed[i].next)
if ((v=ed[i].to)!=fa[x][0])
fa[v][0]=t[v].fa=x,dfs(v,dth+1);
R[x]=ti;
}
V Make(){
for (int j=1;j<=17;j++)
for (int i=1;i<=n;i++)
fa[i][j]=fa[fa[i][j-1]][j-1];
}
F int lca(int x,int y){
if (dep[x]<dep[y]) swap(x,y);
for (int j=17;~j;j--)
if (dep[fa[x][j]]>=dep[y])
x=fa[x][j];
if (x==y) return x;
for (int j=17;~j;j--) if (fa[x][j]!=fa[y][j]) x=fa[x][j],y=fa[y][j];
return fa[x][0];
}
//以上为求DFS序和LCA
V pshd(int x){
s[x<<1].tg+=s[x].tg,s[x<<1|1].tg+=s[x].tg;
s[x<<1].mx+=s[x].tg,s[x<<1|1].mx+=s[x].tg,s[x].tg=0;
}
void build(int x,int l,int r){
s[x].l=l,s[x].r=r; int mid=l+r>>1;
if (l==r) return (void)(s[x].mx=dep[id[l]]);
build(x<<1,l,mid),build(x<<1|1,mid+1,r);
s[x].mx=max(s[x<<1].mx,s[x<<1|1].mx);
}
void mdfy(int x,int l,int r,int w){
int L=s[x].l,R=s[x].r; if (L>r||R<l) return;
if (L>=l&&R<=r) return s[x].tg+=w,(void)(s[x].mx+=w);
if (s[x].tg) pshd(x); mdfy(x<<1,l,r,w),mdfy(x<<1|1,l,r,w);
s[x].mx=max(s[x<<1].mx,s[x<<1|1].mx);
}
int srch(int x,int l,int r){
int L=s[x].l,R=s[x].r; if (L>=l&&R<=r) return s[x].mx;
if (L>r||R<l) return 0; if (s[x].tg) pshd(x);
return max(srch(x<<1,l,r),srch(x<<1|1,l,r));
}
//以上为线段树
#define rt(x) (t[t[x].fa].to[0]!=(x)&&t[t[x].fa].to[1]!=(x))
V rtt(int x){
int y=t[x].fa,z=t[y].fa,l=(t[y].to[1]!=x);
if (!rt(y)) t[z].to[t[z].to[0]!=y]=x;
t[x].fa=z,t[y].fa=x,t[t[x].to[l]].fa=y;
t[y].to[l^1]=t[x].to[l],t[x].to[l]=y;
}
V splay(int x){
for (int y=t[x].fa,z=t[y].fa;!rt(x);rtt(x),z=t[y=t[x].fa].fa)
if (!rt(y)) rtt(((t[y].to[0]==x)^(t[z].to[0]==y))?x:y);
}
V ccss(int x){
for (int i=0,z;x;x=t[i=x].fa){
splay(x); int &y=t[x].to[1];
if (y){ for (z=y;t[z].to[0];z=t[z].to[0]); mdfy(1,L[z],R[z],1); }
//如果有右儿子，那么找到它真正的儿子，以它儿子为根的子树的虚边多了1
if (i){ for (z=i;t[z].to[0];z=t[z].to[0]); mdfy(1,L[z],R[z],-1); }
//如果当前节点存在，那么找到它真正的儿子，以它儿子为根的子树的虚边少了1
y=i;
}
}
//以上为LCT
#define calc(x) (srch(1,L[x],L[x]))
V addedge(int x,int y){ ed[++k]=(edge){h[x],y},h[x]=k; }
int main(){
n=_read(),m=_read(); int x,y;
for (int i=1;i<n;i++) x=_read(),y=_read(),addedge(x,y),addedge(y,x);
dfs(1,1),build(1,1,n),Make(); int f,z;
while (m--){
switch (f=_read()){
case 1: ccss(_read()); break;
case 2: x=_read(),y=_read();
_write(calc(x)+calc(y)-(calc(lca(x,y))<<1)+1);
break;
case 3: x=_read(),_write(srch(1,L[x],R[x]));
}
}
return 0;
}
