Description
Bob有一棵n个点的有根树，其中1号点是根节点。Bob在每个点上涂了颜色，并且每个点上的颜色不同。定义一条路
径的权值是：这条路径上的点（包括起点和终点）共有多少种不同的颜色。Bob可能会进行这几种操作：
1 x:
把点x到根节点的路径上所有的点染上一种没有用过的新颜色。
2 x y:
求x到y的路径的权值。
3 x
在以x为根的子树中选择一个点，使得这个点到根节点的路径权值最大，求最大权值。
Bob一共会进行m次操作
Input
第一行两个数n,m。
接下来n-1行，每行两个数a,b，表示a与b之间有一条边。
接下来m行，表示操作，格式见题目描述
1<=n,m<=100000
Output
每当出现2,3操作，输出一行。
如果是2操作，输出一个数表示路径的权值
如果是3操作，输出一个数表示权值的最大值
Sample Input
5 6
1 2
2 3
3 4
3 5
2 4 5
3 3
1 4
2 4 5
1 5
2 4 5
1 2
2 3
3 4
3 5
2 4 5
3 3
1 4
2 4 5
1 5
2 4 5
Sample Output
3
4
2
2
4
2
2
解题思路：
LCT好题access构造。
将第一个操作视为access操作并更新答案。
那么开始时视为没有轻重链。
access过程中若发生轻重链转化时将子树答案都加1，并撤销上一节点操作。
这样就可以在每一个节点上维护到根的权值和。
第三问直接解决。
第二问呢，发现合并两条链的代价就是两个链单独的代价-2*lca代价+1（因为lca节点需要考虑）
子树修改普通Dfs就好了。
代码：
#include<cstdio>
#include<cstring>
#include<algorithm>
#define lll tr[spc].ch[0]
#define rrr tr[spc].ch[1]
#define ls ch[0]
#define rs ch[1]
typedef long long lnt;
const int N=;
struct seg_trnt{
int lzt;
int maxval;
}ter[N<<];
struct spl_trnt{
int ch[];
int fa;
int lzt;
bool anc;
}tr[N];
struct pnt{
int hd;
int dp;
int ind;
int oud;
int fa[];
}p[N];
struct ent{
int twd;
int lst;
}e[N<<];
int n,m;
int cnt;
int dfn;
bool sta=true;
int pos[N];
void pushup(int spc)
{
ter[spc].maxval=std::max(ter[spc<<].maxval,ter[spc<<|].maxval);
return ;
}
void ppushdown(int spc)
{
if(ter[spc].lzt)
{
ter[spc<<].maxval+=ter[spc].lzt;
ter[spc<<|].maxval+=ter[spc].lzt;
ter[spc<<].lzt+=ter[spc].lzt;
ter[spc<<|].lzt+=ter[spc].lzt;
ter[spc].lzt=;
}
return ;
}
void update(int l,int r,int ll,int rr,int spc,int v)
{
if(ll>r||l>rr)
return ;
if(ll<=l&&r<=rr)
{
ter[spc].maxval+=v;
ter[spc].lzt+=v;
return ;
}
ppushdown(spc);
int mid=(l+r)>>;
update(l,mid,ll,rr,spc<<,v);
update(mid+,r,ll,rr,spc<<|,v);
pushup(spc);
return ;
}
int maxq(int l,int r,int ll,int rr,int spc)
{
if(ll>r||l>rr)
return -0x3f3f3f3f;
if(ll<=l&&r<=rr)
return ter[spc].maxval;
int mid=(l+r)>>;
ppushdown(spc);
return std::max(maxq(l,mid,ll,rr,spc<<),maxq(mid+,r,ll,rr,spc<<|));
}
int query(int l,int r,int pos,int spc)
{
if(l==r)
return ter[spc].maxval;
ppushdown(spc);
int mid=(l+r)>>;
if(pos<=mid)
return query(l,mid,pos,spc<<);
return query(mid+,r,pos,spc<<|);
}
void build(int l,int r,int spc)
{
if(l==r)
{
ter[spc].maxval=p[pos[l]].dp;
return ;
}
int mid=(l+r)>>;
build(l,mid,spc<<);
build(mid+,r,spc<<|);
pushup(spc);
return ;
}
void ade(int f,int t)
{
cnt++;
e[cnt].twd=t;
e[cnt].lst=p[f].hd;
p[f].hd=cnt;
return ;
}
void dfs(int x,int f)
{
p[x].dp=p[f].dp+;
p[x].fa[]=f;
pos[++dfn]=x;
p[x].ind=dfn;
for(int i=;i<=;i++)
p[x].fa[i]=p[p[x].fa[i-]].fa[i-];
for(int i=p[x].hd;i;i=e[i].lst)
{
int to=e[i].twd;
if(to==f)
continue;
tr[to].fa=x;
dfs(to,x);
}
p[x].oud=dfn;
return ;
}
int Lca(int x,int y)
{
if(p[x].dp<p[y].dp)
std::swap(x,y);
for(int i=;i>=;i--)
{
if(p[p[x].fa[i]].dp>=p[y].dp)
x=p[x].fa[i];
}
if(x==y)
return x;
for(int i=;i>=;i--)
{
if(p[x].fa[i]!=p[y].fa[i])
x=p[x].fa[i],y=p[y].fa[i];
}
return p[x].fa[];
}
bool whc(int spc)
{
return tr[tr[spc].fa].rs==spc;
}
void trr(int spc)
{
if(!spc)
return ;
std::swap(lll,rrr);
tr[spc].lzt^=;
return ;
}
void pushdown(int spc)
{
if(tr[spc].lzt)
{
tr[spc].lzt=;
trr(lll);
trr(rrr);
}
return ;
}
void recal(int spc)
{
if(!tr[spc].anc)
recal(tr[spc].fa);
pushdown(spc);
return ;
}
void rotate(int spc)
{
int f=tr[spc].fa;
bool k=whc(spc);
tr[f].ch[k]=tr[spc].ch[!k];
tr[spc].ch[!k]=f;
if(tr[f].anc)
{
tr[f].anc=;
tr[spc].anc=;
}else
tr[tr[f].fa].ch[whc(f)]=spc;
tr[spc].fa=tr[f].fa;
tr[f].fa=spc;
tr[tr[f].ch[k]].fa=f;
return ;
}
void splay(int spc)
{
recal(spc);
while(!tr[spc].anc)
{
int f=tr[spc].fa;
if(tr[f].anc)
{
rotate(spc);
return ;
}
if(whc(spc)^whc(f))
rotate(spc);
else
rotate(f);
rotate(spc);
}
return ;
}
int leftpos(int spc)
{
pushdown(spc);
while(lll)
{
spc=lll;
pushdown(spc);
}
return spc;
}
void access(int spc)
{
int lst=,x;
while(spc)
{
splay(spc);
tr[lst].anc=;
tr[rrr].anc=;
x=leftpos(rrr);
if(x&&!sta)
update(,n,p[x].ind,p[x].oud,,);
x=leftpos(lst);
if(x&&!sta)
update(,n,p[x].ind,p[x].oud,,-);
rrr=lst;
lst=spc;
spc=tr[spc].fa;
}
return ;
}
void Mtr(int spc)
{
access(spc);
splay(spc);
trr(spc);
return ;
}
void split(int x,int y)
{
Mtr(x);
access(y);
splay(y);
return ;
}
void link(int x,int y)
{
split(x,y);
tr[x].fa=y;
return ;
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=;i<=n;i++)
{
tr[i].anc=true;
}
for(int i=;i<n;i++)
{
int a,b;
scanf("%d%d",&a,&b);
ade(a,b);
ade(b,a);
}
dfs(,);
build(,n,);
sta=false;
while(m--)
{
int cmd;
scanf("%d",&cmd);
if(cmd==)
{
int x;
scanf("%d",&x);
Mtr();
access(x);
}else if(cmd==)
{
int ans=;
int x,y;
scanf("%d%d",&x,&y);
int z=Lca(x,y);
ans+=query(,n,p[x].ind,);
ans+=query(,n,p[y].ind,);
ans-=query(,n,p[z].ind,)<<;
printf("%d\n",ans);
}else{
int x;
scanf("%d",&x);
printf("%d\n",maxq(,n,p[x].ind,p[x].oud,));
}
}
return ;
}