抄题解.jpg
当是用来复习(LCT)的了
发现一操作很具有灵性，把一个点到根的路径涂上一种新颜色，这里的新颜色竟然和之前的都不同，那么所有的颜色必然都会是一段深度连续的路径了
既然是暴力到根，那么我们就会发现这个和(lct)的(access)操作很像啊；而且每段颜色都是一段深度连续的路径，而一个(splay)里维护的也就是这些东西
于是我们可以直接使用(lct)来维护第一问，直接(access)上去把这个点到根的路径都搞到一个(splay)中去，这样一个(splay)里维护的就是颜色相同的一段路径
面对二操作，好像这是一个树剖操作啊，但是我们发现这里的同一颜色都是深度连续的，于是可以考虑使用树上差分，也就是(pre_x+pre_y-2 imes pre_{lca}+1)，(+1)是因为(lca)被减了两次
考虑在(access)的同时维护出这个东西
回顾我们的(access)操作，板子里是这样写的
for(int y=0;x;y=x,f=fa[x])
splay(x),ch[x][1]=y,pushup(x);
发现我们就是不断重复断掉(x)和之前的深度比它大的点之间的关系，连上一个新的儿子
断掉那个之前的深度更大的儿子，显然那个儿子就自己变成了一个(splay)的根了，这个(splay)以及下面的其余(splay)发现上面都出现了一个新的颜色，于是这个子树的(pre)都应该加(1)
连上新的儿子，新的儿子原来的那棵(splay)就消失了了，和当前的(splay)合并在一起了，于是我们应该把这棵子树的答案减(1)
于是我们(dfn)+线段树维护一下就好了
三操作就是查一个子树最大值，没了
代码
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#define re register
#define LL long long
const int maxn=100005;
inline int read() {
char c=getchar();int x=0;while(c<'0'||c>'9') c=getchar();
while(c>='0'&&c<='9') x=(x<<3)+(x<<1)+c-48,c=getchar();return x;
}
struct E{int v,nxt;}e[maxn<<1];
inline int max(int a,int b) {return a>b?a:b;}
int ch[maxn][2],fa[maxn],f[maxn],deep[maxn],dfn[maxn],id[maxn];
int head[maxn],son[maxn],sum[maxn],top[maxn];
int l[maxn<<2],r[maxn<<2],tag[maxn<<2],mx[maxn<<2];
int n,m,num,__;
inline void add(int x,int y) {e[++num].v=y;e[num].nxt=head[x];head[x]=num;}
inline void pushup(int x) {mx[x]=max(mx[x<<1],mx[x<<1|1]);}
void build(int x,int y,int i) {
l[i]=x,r[i]=y;
if(x==y) {mx[i]=deep[id[x]];return;}
int mid=x+y>>1;
build(x,mid,i<<1);build(mid+1,y,i<<1|1);
pushup(i);
}
inline void pushdown(int i) {
if(!tag[i]) return;
tag[i<<1]+=tag[i],tag[i<<1|1]+=tag[i];
mx[i<<1]+=tag[i];mx[i<<1|1]+=tag[i];
tag[i]=0;
}
void change(int x,int y,int i,int val) {
if(x<=l[i]&&y>=r[i]) {
mx[i]+=val;tag[i]+=val;
return;
}
pushdown(i);
int mid=l[i]+r[i]>>1;
if(x<=mid) change(x,y,i<<1,val);
if(y>mid) change(x,y,i<<1|1,val);
pushup(i);
}
int query(int x,int y,int i) {
if(x<=l[i]&&y>=r[i]) return mx[i];
pushdown(i);
int mid=l[i]+r[i]>>1,now=0;
if(x<=mid) now=max(now,query(x,y,i<<1));
if(y>mid) now=max(now,query(x,y,i<<1|1));
return now;
}
int ask(int pos,int i) {
if(l[i]==r[i]) return mx[i];
pushdown(i);
int mid=l[i]+r[i]>>1;
if(pos<=mid) return ask(pos,i<<1);
return ask(pos,i<<1|1);
}
inline void Add(int x,int val) {change(dfn[x],dfn[x]+sum[x]-1,1,val);}
inline int nroot(int x) {return ch[fa[x]][0]==x||ch[fa[x]][1]==x;}
inline void rotate(int x) {
int y=fa[x],z=fa[y],k=ch[y][1]==x,w=ch[x][k^1];
if(nroot(y)) ch[z][ch[z][1]==y]=x;
ch[x][k^1]=y,ch[y][k]=w;
fa[w]=y,fa[y]=x,fa[x]=z;
}
inline void splay(int x) {
while(nroot(x)) {
int y=fa[x];
if(nroot(y)) rotate((ch[y][1]==x)^(ch[fa[y]][1]==y)?x:y);
rotate(x);
}
}
inline int frt(int x) {
while(ch[x][0]) x=ch[x][0];
return x;
}
inline void access(int x) {
for(re int y=0;x;y=x,x=fa[x]) {
splay(x);
if(ch[x][1]) Add(frt(ch[x][1]),1);
if(y) Add(frt(y),-1);
ch[x][1]=y;
}
}
void dfs1(int x) {
sum[x]=1;int maxx=-1;
for(re int i=head[x];i;i=e[i].nxt) {
if(deep[e[i].v]) continue;
deep[e[i].v]=deep[x]+1;f[e[i].v]=fa[e[i].v]=x;
dfs1(e[i].v);sum[x]+=sum[e[i].v];
if(sum[e[i].v]>maxx) son[x]=e[i].v,maxx=sum[e[i].v];
}
}
void dfs2(int x,int topf) {
top[x]=topf;dfn[x]=++__,id[__]=x;
if(!son[x]) return;
dfs2(son[x],topf);
for(re int i=head[x];i;i=e[i].nxt)
if(!top[e[i].v]) dfs2(e[i].v,e[i].v);
}
inline int LCA(int x,int y) {
while(top[x]!=top[y]) {
if(deep[top[x]]<deep[top[y]]) std::swap(x,y);
x=f[top[x]];
}
if(deep[x]<deep[y]) return x;return y;
}
int main() {
n=read(),m=read();
for(re int x,y,i=1;i<n;i++)
x=read(),y=read(),add(x,y),add(y,x);
deep[1]=1,dfs1(1),dfs2(1,1),build(1,n,1);
int opt,x,y;
while(m--) {
opt=read(),x=read();
if(opt==1) access(x);
if(opt==2)
y=read(),printf("%d
",ask(dfn[x],1)+ask(dfn[y],1)-2*ask(dfn[LCA(x,y)],1)+1);
if(opt==3)
printf("%d
",query(dfn[x],dfn[x]+sum[x]-1,1));
}
return 0;
}