[BZOJ]4817: [Sdoi2017]树点涂色

Time Limit: 10 Sec  Memory Limit: 128 MB

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

Sample Output

　　3
　　4
　　2
　　2

Solution

　　发现这个修改操作像极了LCT，于是我们直接用LCT维护这棵树，每棵Splay代表一种颜色，每个点到根的权值就是到根路径上非偏爱边（这里非偏爱边相当于两端颜色不同的边）数量加一，一开始所有点的权值就是深度，当进行access操作时，我们每把一条偏爱边设成非偏爱边，就让这条边下面那棵子树权值加一，反之减一，以dfs序建线段树维护最大值即可，1操作直接access一遍，2操作等同于询问链上非偏爱边数加一，链上非偏爱边数即x到根的非偏爱边数+y到根的非偏爱边数-2*lca(x,y)到根的偏爱边数，3操作直接查。由于LCT是均摊O(nlogn)的，我们往里面每次操作都加了一个维护线段树的工作，总复杂度O(nlogn^2)。

Code

#include<cstdio>
#include<algorithm>
using namespace std;
char B[1<<26],*S=B,C;int X;
inline int read()
{
    while((C=*S++)<'0'||C>'9');
    for(X=C-'0';(C=*S++)>='0'&&C<='9';)X=X*10+C-'0';
    return X;
}
#define MN 100000
#define LG 17
struct edge{int nx,t;}e[MN*2+5];
int h[MN+5],en,fa[LG][MN+5],d[MN+5],a[MN+5],l[MN+5],r[MN+5],cnt;
inline void ins(int x,int y)
{
    e[++en]=(edge){h[x],y};h[x]=en;
    e[++en]=(edge){h[y],x};h[y]=en;
}
namespace segtree
{
    #define L (k<<1)
    #define R (k<<1|1)
    struct node{int l,r,mx,mk;}t[MN*4+5];
    inline void up(int k){t[k].mx=max(t[L].mx,t[R].mx);}
    inline void mark(int k,int x){t[k].mx+=x;t[k].mk+=x;}
    inline void down(int k){if(t[k].mk)mark(L,t[k].mk),mark(R,t[k].mk),t[k].mk=0;}
    void build(int k,int l,int r)
    {
        if((t[k].l=l)==(t[k].r=r)){t[k].mx=a[l];return;}
        int mid=l+r>>1;
        build(L,l,mid);build(R,mid+1,r);up(k);
    }
    void add(int k,int l,int r,int x)
    {
        if(t[k].l==l&&t[k].r==r){mark(k,x);return;}
        int mid=t[k].l+t[k].r>>1;down(k);
        if(r<=mid)add(L,l,r,x);
        else if(l>mid)add(R,l,r,x);
        else add(L,l,mid,x),add(R,mid+1,r,x);
        up(k);
    }
    int query(int k,int l,int r)
    {
        if(t[k].l==l&&t[k].r==r)return t[k].mx;
        int mid=t[k].l+t[k].r>>1;down(k);
        if(r<=mid)return query(L,l,r);
        if(l>mid)return query(R,l,r);
        return max(query(L,l,mid),query(R,mid+1,r));
    }
}
namespace lct
{
    #define L(x) c[x][0]
    #define R(x) c[x][1]
    int fa[MN+5],c[MN+5][2],ll[MN+5];
    inline void up(int x){ll[x]=L(x)?ll[L(x)]:x;}
    inline bool isc(int x){return L(fa[x])==x||R(fa[x])==x;}
    void rotate(int x)
    {
        int f=fa[x],ff=fa[f],l=R(f)==x,r=l^1;
        if(isc(f))c[ff][R(ff)==f]=x;
        fa[f]=x;fa[x]=ff;fa[c[x][r]]=f;
        c[f][l]=c[x][r];up(c[x][r]=f);
    }
    void splay(int x)
    {
        for(int f;isc(x);rotate(x))
            if(isc(f=fa[x]))rotate(L(fa[f])==f^L(f)==x?x:f);
        up(x);
    }
    void access(int x)
    {
        for(int i=0,p;x;x=fa[i=x])
        {
            splay(x);
            if(R(x))segtree::add(1,l[ll[R(x)]],r[ll[R(x)]],1);
            if(i)segtree::add(1,l[ll[i]],r[ll[i]],-1);
            R(x)=i;
        }
    }
}
void dfs(int x)
{
    a[l[x]=++cnt]=d[x];
    for(int i=h[x];i;i=e[i].nx)if(e[i].t!=fa[0][x])
        lct::fa[e[i].t]=fa[0][e[i].t]=x,d[e[i].t]=d[x]+1,dfs(e[i].t);
    r[x]=cnt;
}
int lca(int x,int y)
{
    int dx=d[x]-d[y],i;
    if(dx<0)swap(x,y),dx=-dx;
    for(i=0;dx;++i,dx>>=1)if(dx&1)x=fa[i][x];
    if(x==y)return x;
    for(i=LG;i--;)if(fa[i][x]!=fa[i][y])x=fa[i][x],y=fa[i][y];
    return fa[0][x];
}
int main()
{
    fread(B,1,1<<26,stdin);
    int n,m,i,j,x,y,z;
    n=read();m=read();
    for(i=1;i<n;++i)ins(read(),read());
    dfs(1);segtree::build(1,1,n);
    for(i=1;i<LG;++i)for(j=1;j<=n;++j)fa[i][j]=fa[i-1][fa[i-1][j]];
    using segtree::query;
    while(m--)
    {
        i=read();
        if(i==1)lct::access(read());
        if(i==2)z=lca(x=read(),y=read()),
            printf("%d\n",query(1,l[x],l[x])+query(1,l[y],l[y])-(query(1,l[z],l[z])<<1)+1);
        if(i==3)x=read(),printf("%d\n",query(1,l[x],r[x])+1);
    }
}