LINK：树点涂色
还是由暴力的思路拓展出来。可以发现对于初始情况一个点的权值就是深度。
可以发现每次1操作是 LCT的access操作。
考虑2操作 求x到y的权值和。
可以发现其实是求x的答案+y的答案-2*LCA(x,y)的答案+1
为什么 考虑 lca和他们两条路径上的最后一个点颜色都不同 那么这样做显然少加了一个LCA的颜色。
如果和他们其中一个相同 这样做 发现也少加了一个LCA的颜色。
至于操作3 直接维护区间最大值即可。
const int MAXN=100010;
int n,Q,len,cnt;
int lin[MAXN],c[MAXN][2],f[MAXN],ver[MAXN<<1],nex[MAXN<<1],dfn[MAXN],out[MAXN];
int fa[MAXN],d[MAXN],sz[MAXN],son[MAXN],top[MAXN],v[MAXN];
inline void add(int x,int y)
{
ver[++len]=y;
nex[len]=lin[x];
lin[x]=len;
}
inline void dfs(int x,int father)
{
sz[x]=1;fa[x]=father;d[x]=d[father]+1;
go(x)if(tn^father)
{
dfs(tn,x);
sz[x]+=sz[tn];
if(sz[tn]>sz[son[x]])son[x]=tn;
}
}
inline void dp(int x,int father)
{
top[x]=father;dfn[x]=++cnt;v[cnt]=x;
if(son[x])dp(son[x],father);
go(x)if(tn!=fa[x]&&tn!=son[x])dp(tn,tn);
out[x]=cnt;
}
inline int LCA(int x,int y)
{
while(top[x]^top[y])
{
if(d[top[x]]<d[top[y]])swap(x,y);
x=fa[top[x]];
}
return d[x]<d[y]?x:y;
}
struct seg{int tag,mx,l,r;}t[MAXN<<2];
inline void spread(int p,int v){tag(p)+=v;mx(p)+=v;}
inline void pushdown(int p)
{
spread(zz,tag(p));
spread(yy,tag(p));
tag(p)=0;
}
inline void build(int p,int l,int r)
{
l(p)=l;r(p)=r;
if(l==r){mx(p)=d[v[l]];return;}
int mid=(l+r)>>1;
build(zz,l,mid);build(yy,mid+1,r);
mx(p)=max(mx(zz),mx(yy));
}
inline void change(int p,int l,int r,int x)
{
if(l<=l(p)&&r>=r(p)){spread(p,x);return;}
int mid=(l(p)+r(p))>>1;
if(tag(p))pushdown(p);
if(l<=mid)change(zz,l,r,x);
if(r>mid)change(yy,l,r,x);
mx(p)=max(mx(zz),mx(yy));
}
inline int ask(int p,int x)
{
if(l(p)==r(p))return mx(p);
int mid=(l(p)+r(p))>>1;
if(tag(p))pushdown(p);
if(x<=mid)return ask(zz,x);
return ask(yy,x);
}
inline int ask(int p,int l,int r)
{
if(l<=l(p)&&r>=r(p))return mx(p);
int mid=(l(p)+r(p))>>1,w=0;
if(tag(p))pushdown(p);
if(l<=mid)w=ask(zz,l,r);
if(r>mid)w=max(w,ask(yy,l,r));
return w;
}
inline int pd(int x){return c[f[x]][1]==x||c[f[x]][0]==x;}//判断x是否为根.
inline void rotate(int x)
{
int old=f[x],oldf=f[old],k=c[old][1]==x;
c[old][k]=c[x][k^1];c[x][k^1]=old;
if(pd(old))c[oldf][c[oldf][1]==old]=x;
if(c[old][k])f[c[old][k]]=old;
f[old]=x;f[x]=oldf;
}
inline void splay(int x)
{
while(pd(x))
{
if(pd(f[x]))rotate((c[f[x]][1]==x)^(c[f[f[x]]][1]==f[x])?x:f[x]);
rotate(x);
}
}
inline int findroot(int x)
{
splay(x);
while(c[x][0])x=c[x][0];
splay(x);return x;
}
inline void access(int x)
{
int y=0;
while(x)
{
splay(x);
if(c[x][1])
{
int w=c[x][1];
c[x][1]=0;
w=findroot(w);
change(1,dfn[w],out[w],1);
}
if(y)
{
y=findroot(y);
change(1,dfn[y],out[y],-1);
}
c[x][1]=y;
y=x;x=f[x];
}
}
int main()
{
freopen("1.in","r",stdin);
//freopen("1.out","w",stdout);
get(n);get(Q);
rep(2,n,i)
{
int x,y;
get(x);get(y);
//cout<<x<<' '<<y<<endl;
add(x,y);add(y,x);
}
dfs(1,0);dp(1,1);
build(1,1,n);
rep(1,n,i)f[i]=fa[i];
rep(1,Q,i)
{
int op,x,y;
get(op);get(x);
if(op==1)access(x);
if(op==2)get(y),put(ask(1,dfn[x])+ask(1,dfn[y])-ask(1,dfn[LCA(x,y)])*2+1);
if(op==3)put(ask(1,dfn[x],out[x]));
}
return 0;
}
复杂度nlog^2.