[SDOI 2017] 트 리 포인트 색칠

제목 링크
제목 의 대의
세 가지 조작 이 있 는데,
1. 점 x x x 를 루트 노드 의 경로 에 있 는 모든 점 을 사용 하지 않 은 새로운 색 으로 염색 합 니 다.
2. x x x 에서 y y 까지 의 경로 의 서로 다른 색상 수 를 구 합 니 다.
3. x x x 를 뿌리 로 하 는 서브 트 리 에서 점 하 나 를 선택 하여 이 점 에서 뿌리 노드 까지 의 경로 에 따라 색상 수가 가장 크 고 최대 값 을 구 합 니 다.
문제 풀이 의 사고 방향.
수정 작업 의 한 가지 성질 을 발견 할 수 있다. 모든 색채 의 노드 는 반드시 하나의 체인 을 형성 할 것 이다.
LCT 의 성질 을 이용 하여 access 는 실제 적 으로 특정한 점 과 뿌리의 경 로 를 연결 시 키 고 대응 하 는 동작 1 을 고려 합 니 다. 그리고 한 점 에서 루트 경로 까지 의 가상 변 의 수량 + 1 은 뿌리 까지 의 색상 수 에 대응 합 니 다. 이 색상 수 는 splay 할 때 유지 하면 됩 니 다.
d e p [x] dep [x] dep [x] 로 x x 에서 뿌리 까지 의 색상 수 를 표시 하면 2 를 조작 하 는 답 은 d e p [x] + d e p [y] - 2 * 8727 ° d e p [l c a dep [x] + dep [y] - 2 * dep [lca dep [x] + dep [y] - 2 * 8727 ° dep [lcax, y] + 1] + 1 이다.
조작 을 고려 하면 3. 사실은 서브 트 리 가 d p dep dep 의 최대 치 를 구하 고 나 무 를 하나 로 자 르 면 됩 니 다.
LCT 는 추출 경로 에 만 사용 되 기 때문에 make 가 없습니다.루트 작업, 반전 표 시 를 하지 않 아 도 됩 니 다.
코드

#include
#include
#include
#define N 100010
using namespace std;
int nxt[N<<1],to[N<<1],head[N],cnt;
void add(int u,int v)
{
	nxt[++cnt]=head[u];
	to[cnt]=v;
	head[u]=cnt;
}
int siz[N],dep[N],id[N],nid[N],n,tot;
struct seg_tree{
	int val[N<<2],tag[N<<2];
	void push_down(int u)
	{
		if(!tag[u]) return;
		val[u<<1]+=tag[u];
		val[u<<1|1]+=tag[u];
		tag[u<<1]+=tag[u];
		tag[u<<1|1]+=tag[u];
		tag[u]=0;
	}
	void change(int u,int l,int r,int L,int R,int v)
	{
		if(L<=l && r<=R){val[u]+=v,tag[u]+=v;return;}
		int mid=(l+r)>>1;
		push_down(u);
		if(L<=mid) change(u<<1,l,mid,L,R,v);
		if(R>mid) change(u<<1|1,mid+1,r,L,R,v);
		val[u]=max(val[u<<1],val[u<<1|1]);
	}
	void build(int u,int l,int r)
	{
		if(l==r){val[u]=dep[nid[l]];return;}
		int mid=(l+r)>>1;
		build(u<<1,l,mid);
		build(u<<1|1,mid+1,r);
		val[u]=max(val[u<<1],val[u<<1|1]);
    }
	int answer(int u,int l,int r,int L,int R)
	{
		if(L>r || R<l) return 0;
		if(L<=l && r<=R) return val[u];
		push_down(u);
		int mid=(l+r)>>1;
		return max(answer(u<<1,l,mid,L,R),answer(u<<1|1,mid+1,r,L,R));
	}
}tr;
struct LCT{
	int fa[N],ch[N][2];
//	bool tag[N];
	bool not_root(int u){return ch[fa[u]][0]==u || ch[fa[u]][1]==u;}
//	void set_tag(int u){swap(ch[u][0],ch[u][1]);tag[u]^=1;}
//	void push_down(int u)
//	{
//		if(!tag[u]) return;
//		set_tag(ch[u][0]);
//		set_tag(ch[u][1]);
//		tag[u]=false;
//	}
	void rotate(int u)
	{
		int f=fa[u],ff=fa[f],k=ch[f][1]==u,v=ch[u][!k];
		if(not_root(f)) ch[ff][ch[ff][1]==f]=u;
		ch[u][!k]=f;
		ch[f][k]=v;
		if(v) fa[v]=f;
		fa[f]=u;
		fa[u]=ff;
	}
//	int ton[N];
//	void push_all(int u)
//	{
//		int top=0;
//		ton[++top]=u;
//		while(not_root(u)) ton[++top]=fa[u],u=fa[u];
//		while(top) push_down(ton[top--]);
//	}
	void splay(int u)
	{
//		push_all(u);
		while(not_root(u))
		{
			int f=fa[u],ff=fa[f];
			if(not_root(f)) rotate((ch[f][0]==u)^(ch[ff][0]==f)?u:f);
			rotate(u);
		}
	}
	int find_root(int u)
	{
		while(ch[u][0]) u=ch[u][0];
		return u;
	}
	void access(int u)
	{
		for(int x=0;u;x=u,u=fa[u])
		{
			splay(u);
			if(ch[u][1])
			{
				int v=find_root(ch[u][1]);
				tr.change(1,1,n,id[v],id[v]+siz[v]-1,1);
			}
			ch[u][1]=x;
			if(x)
			{
				int v=find_root(x);
				tr.change(1,1,n,id[v],id[v]+siz[v]-1,-1);
			}
		}
	}
}lct;
int son[N],fa[N],top[N];
void dfs1(int u,int f)
{
	lct.fa[u]=fa[u]=f;
	dep[u]=dep[f]+1;
	siz[u]=1;
	for(int i=head[u];i;i=nxt[i])
	{
		int v=to[i];
		if(v==f)continue;
		dfs1(v,u);
		siz[u]+=siz[v];
		if(siz[son[u]]<siz[v]) son[u]=v;
	}
}
void dfs2(int u,int topp)
{
	id[u]=++tot;
	nid[tot]=u;
	top[u]=topp;
	if(son[u]) dfs2(son[u],topp);
	for(int i=head[u];i;i=nxt[i])
	{
		int v=to[i];
		if(v!=fa[u] && v!=son[u]) dfs2(v,v);
	}
}
int lca(int x,int y)
{
	while(top[x]!=top[y])
	{
		if(dep[top[x]]<dep[top[y]]) swap(x,y);
		x=fa[top[x]];
	}
	if(dep[x]>dep[y]) swap(x,y);
	return x;
}

int main()
{
	int m;
	scanf("%d%d",&n,&m);
	for(int i=1;i<n;i++)
	{
		int u,v;
		scanf("%d%d",&u,&v);
		add(u,v);
		add(v,u);
	}
	dfs1(1,0);
	dfs2(1,1);
	tr.build(1,1,n);
	for(int i=1;i<=m;i++)
	{
		int opt,x,y;
		scanf("%d%d",&opt,&x);
		if(opt==1) lct.access(x);
		else if(opt==2)
		{
			scanf("%d",&y);
			int l=lca(x,y);
			printf("%d
",tr.answer(1,1,n,id[x],id[x])+tr.answer(1,1,n,id[y],id[y])-2*tr.answer(1,1,n,id[l],id[l])+1);
		}
		else printf("%d
",tr.answer(1,1,n,id[x],id[x]+siz[x]-1));
	}
	return 0;
}