题意

Bob有一棵n个点的有根树，其中1号点是根节点。Bob在每个点上涂了颜色，并且每个点上的颜色不同。定义一条路 径的权值是：这条路径上的点（包括起点和终点）共有多少种不同的颜色。Bob可能会进行这几种操作： 1 x: 把点x到根节点的路径上所有的点染上一种没有用过的新颜色。 2 x y: 求x到y的路径的权值。 3 x y: 在以x为根的子树中选择一个点，使得这个点到根节点的路径权值最大，求最大权值。 Bob一共会进行m次操作 1<=n,m<=100000

分析

注意到操作1十分像lct的access操作，于是我们就可以用lct来乱搞。 我们定义lct上实边连的两个点颜色是一样的，虚边连的是不一样的。那么一个点的权值就是其到根的虚边数量+1. 在做access操作的时候，考虑当前节点x，那么x的实边连向的节点的子树权值就会+1，p的子树权值就会-1.注意一定是深度最小的节点，可以在splay上直接找。 那么我们就可以用树链剖分资瓷找lca和维护子树，用splay维护区间加和最大值即可。

思路很棒棒啊。

代码

#include<iostream> #include<cstdio> #include<cstdlib> #include<cstring> #include<algorithm> using namespace std; const int N=100005; int n,m,dep[N],pos[N],fa[N],top[N],size[N],bel[N],cnt,mx[N],last[N],sz; struct edge{int to,next;}e[N*2]; struct Sigtree { struct tree{int mx,tag;}t[N*4]; void build(int d,int l,int r) { if (l==r) { t[d].mx=dep[bel[l]]; return; } int mid=(l+r)/2; build(d*2,l,mid);build(d*2+1,mid+1,r); t[d].mx=max(t[d*2].mx,t[d*2+1].mx); } void pushdown(int d,int l,int r) { if (l==r||!t[d].tag) return; int w=t[d].tag;t[d].tag=0; t[d*2].mx+=w;t[d*2+1].mx+=w; t[d*2].tag+=w;t[d*2+1].tag+=w; } void ins(int d,int l,int r,int x,int y,int z) { if (x>y) return; pushdown(d,l,r); if (l==x&&r==y) { t[d].mx+=z;t[d].tag+=z; return; } int mid=(l+r)/2; ins(d*2,l,mid,x,min(mid,y),z); ins(d*2+1,mid+1,r,max(x,mid+1),y,z); t[d].mx=max(t[d*2].mx,t[d*2+1].mx); } int find(int d,int l,int r,int x) { pushdown(d,l,r); if (l==r) return t[d].mx; int mid=(l+r)/2; if (x<=mid) return find(d*2,l,mid,x); else return find(d*2+1,mid+1,r,x); } int get_max(int d,int l,int r,int x,int y) { if (x>y) return 0; pushdown(d,l,r); if (l==x&&r==y) return t[d].mx; int mid=(l+r)/2; return max(get_max(d*2,l,mid,x,min(y,mid)),get_max(d*2+1,mid+1,r,max(x,mid+1),y)); } }Sig; struct link_cut_tree { struct tree{int l,r,fa;}t[N]; bool isroot(int x) { if (x==t[t[x].fa].l||x==t[t[x].fa].r) return 0; else return 1; } void rttr(int x) { int y=t[x].l; t[x].l=t[y].r;t[t[y].r].fa=x; if (x==t[t[x].fa].l) t[t[x].fa].l=y; else if (x==t[t[x].fa].r) t[t[x].fa].r=y; t[y].fa=t[x].fa; t[x].fa=y;t[y].r=x; } void rttl(int x) { int y=t[x].r; t[x].r=t[y].l;t[t[y].l].fa=x; if (x==t[t[x].fa].l) t[t[x].fa].l=y; else if (x==t[t[x].fa].r) t[t[x].fa].r=y; t[y].fa=t[x].fa; t[x].fa=y;t[y].l=x; } void splay(int x) { while (!isroot(x)) { int p=t[x].fa,g=t[p].fa; if (isroot(p)) { if (x==t[p].l) rttr(p); else rttl(p); return; } if (x==t[p].l) if (p==t[g].l) rttr(g),rttr(p); else rttr(p),rttl(g); else if (p==t[g].r) rttl(g),rttl(p); else rttl(p),rttr(g); } } int findmn(int x) { int y=x; while (x) y=x,x=t[x].l; return y; } void access(int x) { int p=0; while (x) { splay(x); int y=findmn(t[x].r); if (y) Sig.ins(1,1,n,pos[y],mx[y],1); t[x].r=p; y=findmn(p); if (y) Sig.ins(1,1,n,pos[y],mx[y],-1); p=x;x=t[x].fa; } } }lct; void addedge(int u,int v) { e[++cnt].to=v;e[cnt].next=last[u];last[u]=cnt; e[++cnt].to=u;e[cnt].next=last[v];last[v]=cnt; } void dfs1(int x) { dep[x]=dep[fa[x]]+1;size[x]=1; for (int i=last[x];i;i=e[i].next) { if (e[i].to==fa[x]) continue; fa[e[i].to]=x;lct.t[e[i].to].fa=x; dfs1(e[i].to); size[x]+=size[e[i].to]; } } void dfs2(int x,int chain) { top[x]=chain;pos[x]=mx[x]=++sz;bel[sz]=x;int k=0; for (int i=last[x];i;i=e[i].next) if (e[i].to!=fa[x]&&size[e[i].to]>size[k]) k=e[i].to; if (!k) return; dfs2(k,chain); for (int i=last[x];i;i=e[i].next) if (e[i].to!=fa[x]&&e[i].to!=k) dfs2(e[i].to,e[i].to); mx[x]=sz; } int get_lca(int x,int y) { while (top[x]!=top[y]) { if (dep[top[x]]<dep[top[y]]) swap(x,y); x=fa[top[x]]; } return dep[x]<dep[y]?x:y; } int main() { scanf("%d%d",&n,&m); for (int i=1;i<n;i++) { int x,y; scanf("%d%d",&x,&y); addedge(x,y); } dfs1(1); dfs2(1,1); Sig.build(1,1,n); for (int i=1;i<=m;i++) { int op; scanf("%d",&op); if (op==1) { int x; scanf("%d",&x); lct.access(x); } else if (op==2) { int x,y; scanf("%d%d",&x,&y); int lca=get_lca(x,y); printf("%d\n",Sig.find(1,1,n,pos[x])+Sig.find(1,1,n,pos[y])-2*Sig.find(1,1,n,pos[lca])+1); } else { int x; scanf("%d",&x); printf("%d\n",Sig.get_max(1,1,n,pos[x],mx[x])); } } return 0; }