【BZOJ4817】[Sdoi2017]树点涂色
Description
Bob有一棵n个点的有根树，其中1号点是根节点。Bob在每个点上涂了颜色，并且每个点上的颜色不同。定义一条路径的权值是：这条路径上的点（包括起点和终点）共有多少种不同的颜色。Bob可能会进行这几种操作：
1 x:
把点x到根节点的路径上所有的点染上一种没有用过的新颜色。
2 x y:
求x到y的路径的权值。
3 x y:
在以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
题解：做过重组病毒那题再做这题就水了。
发现1操作可以看成LCT的access操作，而一个点到根路径的权值就是该点在LCT中到根路径上的虚边数量。所以我们用LCT模拟这个过程，在access的时候顺便改一下子树内的虚边数量即可。可以用线段树实现。
那么已知了一个点到根路径上的权值，如何求一条路径的权值呢？如果a,b的lca是c，那么自己画画就知道，答案是：a路径的权值+b路径的权值-2*c路径的权值+1。
#include <cstdio>
#include <cstring>
#include <iostream>
#define lson x<<1
#define rson x<<1|1
using namespace std;
const int maxn=100010; struct LCT
{
int ch[2],fa,L;
}s[maxn];
int n,m,cnt;
int fa[19][maxn],to[maxn<<1],next[maxn<<1],head[maxn],Log[maxn],dep[maxn],p[maxn],q[maxn],Q[maxn],sm[maxn<<2],ts[maxn<<2];
inline void add(int a,int b)
{
to[cnt]=b,next[cnt]=head[a],head[a]=cnt++;
}
void dfs(int x)
{
p[x]=++q[0],Q[q[0]]=x;
for(int i=head[x];i!=-1;i=next[i]) if(to[i]!=fa[0][x]) fa[0][to[i]]=x,dep[to[i]]=dep[x]+1,dfs(to[i]);
q[x]=q[0];
}
inline int lca(int a,int b)
{
if(dep[a]<dep[b]) swap(a,b);
for(int i=Log[dep[a]-dep[b]];i>=0;i--) if(dep[fa[i][a]]>=dep[b]) a=fa[i][a];
if(a==b) return a;
for(int i=Log[dep[a]];i>=0;i--) if(fa[i][a]!=fa[i][b]) a=fa[i][a],b=fa[i][b];
return fa[0][a];
}
inline bool isr(int x) {return s[s[x].fa].ch[0]!=x&&s[s[x].fa].ch[1]!=x;}
inline void pushup(int x)
{
if(s[x].ch[0]) s[x].L=s[s[x].ch[0]].L;
else s[x].L=x;
}
inline void rotate(int x)
{
int y=s[x].fa,z=s[y].fa,d=(x==s[y].ch[1]);
if(!isr(y)) s[z].ch[y==s[z].ch[1]]=x;
s[x].fa=z,s[y].fa=x,s[y].ch[d]=s[x].ch[d^1];
if(s[x].ch[d^1]) s[s[x].ch[d^1]].fa=y;
s[x].ch[d^1]=y;
pushup(y),pushup(x);
}
inline void splay(int x)
{
while(!isr(x))
{
int y=s[x].fa,z=s[y].fa;
if(!isr(y))
{
if((x==s[y].ch[0])^(y==s[z].ch[0])) rotate(x);
else rotate(y);
}
rotate(x);
}
}
inline void pushdown(int x)
{
if(ts[x]) sm[lson]+=ts[x],ts[lson]+=ts[x],sm[rson]+=ts[x],ts[rson]+=ts[x],ts[x]=0;
}
void build(int l,int r,int x)
{
if(l==r)
{
sm[x]=dep[Q[l]];
return ;
}
int mid=(l+r)>>1;
build(l,mid,lson),build(mid+1,r,rson);
sm[x]=max(sm[lson],sm[rson]);
}
void updata(int l,int r,int x,int a,int b,int val)
{
if(a<=l&&r<=b)
{
sm[x]+=val,ts[x]+=val;
return ;
}
pushdown(x);
int mid=(l+r)>>1;
if(a<=mid) updata(l,mid,lson,a,b,val);
if(b>mid) updata(mid+1,r,rson,a,b,val);
sm[x]=max(sm[lson],sm[rson]);
}
int query(int l,int r,int x,int a,int b)
{
if(a<=l&&r<=b) return sm[x];
pushdown(x);
int mid=(l+r)>>1;
if(b<=mid) return query(l,mid,lson,a,b);
if(a>mid) return query(mid+1,r,rson,a,b);
return max(query(l,mid,lson,a,b),query(mid+1,r,rson,a,b));
}
inline void sumup(int x,int val) {if(x) updata(1,n,1,p[x],q[x],val);}
inline void access(int x)
{
for(int y=0;x;)
{
splay(x);
sumup(s[s[x].ch[1]].L,1),sumup(s[y].L,-1),s[x].ch[1]=y,pushup(x),y=x,x=s[x].fa;
}
}
inline int rd()
{
int ret=0,f=1; char gc=getchar();
while(gc<'0'||gc>'9') {if(gc=='-') f=-f; gc=getchar();}
while(gc>='0'&&gc<='9') ret=ret*10+gc-'0',gc=getchar();
return ret*f;
}
int main()
{
n=rd(),m=rd();
int i,j,a,b,c,op;
memset(head,-1,sizeof(head));
for(i=1;i<n;i++) a=rd(),b=rd(),add(a,b),add(b,a);
dep[1]=1,dfs(1);
for(i=2;i<=n;i++) Log[i]=Log[i>>1]+1;
for(j=1;(1<<j)<=n;j++) for(i=1;i<=n;i++) fa[j][i]=fa[j-1][fa[j-1][i]];
for(i=1;i<=n;i++) s[i].fa=fa[0][i],s[i].L=i;
build(1,n,1);
for(i=1;i<=m;i++)
{
op=rd(),a=rd();
if(op==1) access(a),splay(a);
if(op==2)
{
b=rd(),c=lca(a,b);
printf("%d\n",query(1,n,1,p[a],p[a])+query(1,n,1,p[b],p[b])-2*query(1,n,1,p[c],p[c])+1);
}
if(op==3) printf("%d\n",query(1,n,1,p[a],q[a]));
}
return 0;
}//5 3 1 2 2 3 3 4 3 5 1 4 1 5 2 4 5