题解 P3703 【[SDOI2017]树点涂色】
Newuser
2018-04-11 16:15:34
//本蒟蒻博客的同步阅读：[Newuser小站！](http://www.newuser.top/2018/04/11/shudiantuse/)
这不是纯种的LCT，，，，是LCT+LCA+DFS序（或者重链剖分）+线段树，最近学的全用进来了，，很有喧宾夺主的意味。。。
首先他是每一次都涂一种不同的颜色，就不用具体存储具体的颜色。 我们看到第1个操作，这和LCT的ACCESE很有相似之处。于是我们就想到，设定一个SPLAY就是一个颜色集合的话，那么这个操作1就是一个裸的ACCES操作就好了
第2个操作求AB两点间的路径上的权值，转化为节点到根经过了多少个splay，num[x]，num[a]+num[b]-num[lca(a,b)]*2+1 第3个操作求子树里面的最大num，可以dfs序+线段树维护。 设定num[x]为从x节点开始，往上走到根经过了多少个splay，在开始的时候所有节点都各自为一个splay,此时的num[x]就是每一个节点的深度dep，在dfs的时候就可以搞出来。 想到这个LCT,没有link,没有cut，只有虚实边的转化，于是乎只有Acces会调整他的num值（切换左右儿子的时候）。考虑到每连上去一条边，原本连到的那个结点（切换点的后继）的子树从 id[x]到id[x]+siz[x]-1都会加上一个1（多了一个虚边多了一个到根节点的splay）,之后连到的那个结点的id[x]+siz[x]-1都会减去一个1。
我们考虑线段树维护其区间max，每次ACCES加减就是max的区间修改，而第三问则直接询问子树上的区间Max。
注意我们splay维护的dfs序，在考虑切换重边的时候要考虑到找到深度最小的点（因为这个卡了两个小时的蒟蒻）。
要找LCA，由于这其实是一个静态的树，我们可以LCA转RMQ，，由于本蒟蒻很弱，直接写的倍增。。。
于是就搞定啦！
code:
```cpp
#include<stdio.h>
#include<bits/stdc++.h>
#define midd ((l+r)>>1)
#define zig(x) zigzag(x,1)
#define zag(x) zigzag(x,2)
using namespace std;
int n,m;
int owo,la[100005],nt[200005],en[200005];
void addedge(int a,int b)
{
en[++owo]=b; nt[owo]=la[a]; la[a]=owo;
}
int idcnt,id[100005],old[100005],maxr[100005],dep[100005];
int fa[100005],ls[100005],rs[100005];
struct node
{
int ll,rr,mx,lazy;
}z[8*100005];
void maketree(int p,int l,int r)
{
z[p].ll=l; z[p].rr=r;
if(l==r) { z[p].mx=dep[old[l]]; return; }
maketree(p<<1,l,midd);
maketree(p<<1|1,midd+1,r);
z[p].mx=max(z[p<<1].mx,z[p<<1|1].mx);
}
void ppd(int p)
{
if(z[p].ll==z[p].rr||(!z[p].lazy)) return;
z[p<<1].lazy+=z[p].lazy;
z[p<<1|1].lazy+=z[p].lazy;
z[p<<1].mx+=z[p].lazy;
z[p<<1|1].mx+=z[p].lazy;
z[p].lazy=0;
}
bool isroot(int x) { return ((!fa[x])||(ls[fa[x]]!=x&&rs[fa[x]]!=x)); }
void zigzag(int x,int knd)
{
int y=fa[x]; int z=fa[y];
if(!isroot(y))
{
if(ls[z]==y) ls[z]=x;
else rs[z]=x;
}
fa[x]=z; fa[y]=x;
if(knd==1)
{
ls[y]=rs[x];
fa[ls[y]]=y;
rs[x]=y;
}
else
{
rs[y]=ls[x];
fa[rs[y]]=y;
ls[x]=y;
}
}
void splay(int x)
{
int y,z;
while(!isroot(x))
{
y=fa[x]; z=fa[y];
if(isroot(y))
{
if(ls[y]==x) zig(x);
else zag(x);
}
else
{
if(ls[z]==y)
{
if(ls[y]==x) { zig(y); zig(x); }
else { zag(x); zig(x); }
}
else
{
if(rs[y]==x) { zag(y); zag(x); }
else { zig(x); zag(x); }
}
}
}
}
void update(int p,int x,int y,int d)
{
if(x<=z[p].ll&&z[p].rr<=y) { z[p].mx+=d; z[p].lazy+=d; return; }
if(z[p].lazy) ppd(p);
if(z[p<<1].rr>=x&&z[p<<1].ll<=y) update(p<<1,x,y,d);
if(z[p<<1|1].rr>=x&&z[p<<1|1].ll<=y) update(p<<1|1,x,y,d);
z[p].mx=max(z[p<<1|1].mx,z[p<<1].mx);
}
int mmm(int x)
{
while(ls[x]) x=ls[x];
return x;
}
void acc(int x)
{
for(int y=0;x;y=x,x=fa[x])
{
splay(x);
if(rs[x])
{
int z=mmm(rs[x]);
update(1,id[z],maxr[z],1);
}
rs[x]=y;
if(y)
{
int z=mmm(y);
update(1,id[z],maxr[z],-1);
}
}
}
int getmax(int p,int x,int y)
{
if(x<=z[p].ll&&z[p].rr<=y) return z[p].mx;
if(z[p].lazy) ppd(p);
int lmax=-0x3f3f3f3f,rmax=-0x3f3f3f3f;
if(z[p<<1].rr>=x&&z[p<<1].ll<=y) lmax=getmax(p<<1,x,y);
if(z[p<<1|1].rr>=x&&z[p<<1|1].ll<=y) rmax=getmax(p<<1|1,x,y);
return max(lmax,rmax);
}
int pa[100005][30];
int lcaa(int x,int y)
{
if(dep[x]<dep[y]) swap(x,y);
for(int k=dep[x]-dep[y],i=0;k;i++,k>>=1)
{
if(k&1) x=pa[x][i];
}
if(x==y) return x;
for(int k=20;k>=0;k--)
{
if(pa[x][k]!=pa[y][k]) { x=pa[x][k]; y=pa[y][k]; }
}
return pa[x][0];
}
void dfs(int x,int ba)
{
pa[x][0]=ba;
dep[x]=dep[ba]+1;
for(int k=20,i=1;i<=k;i++) pa[x][i]=pa[pa[x][i-1]][i-1];
fa[x]=ba;
id[x]=++idcnt;
old[idcnt]=x;
for(int it=la[x];it;it=nt[it])
{
if(en[it]!=ba)
{
dfs(en[it],x);
}
}
maxr[x]=idcnt;
}
int query(int p,int x)
{
if(z[p].ll==z[p].rr) return z[p].mx;
if(z[p].lazy) ppd(p);
if(x<=z[p<<1].rr) return query(p<<1,x);
else return query(p<<1|1,x);
}
int main()
{
// freopen("date.in","r",stdin);
// freopen("zhengjie.out","w",stdout);
int a,b;
scanf("%d%d",&n,&m);
for(int i=1;i<n;i++)
{
scanf("%d%d",&a,&b); addedge(a,b); addedge(b,a);
}
dfs(1,0);
maketree(1,1,n);
int kkk,x;
for(int i=1;i<=m;i++)
{
scanf("%d",&kkk);
if(kkk==1)
{
scanf("%d",&x);
acc(x);
}
else if(kkk==2)
{
scanf("%d%d",&a,&b);
int aha=lcaa(a,b);
int aaaa=query(1,id[a])+query(1,id[b])-query(1,id[aha])*2+1;
printf("%d\n",aaaa);
}
else
{
scanf("%d",&a);
printf("%d\n",getmax(1,id[a],maxr[a]));
}
}
}
```