bzoj 4817: [Sdoi2017]树点涂色 link cut tree+线段树+树链剖分

题意

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=;

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)/;
        build(d*2,l,mid);build(d*2+,mid+,r);
        t[d].mx=max(t[d*2].mx,t[d*2+].mx);
    }

    void pushdown(int d,int l,int r)
    {
        if (l==r||!t[d].tag) return;
        int w=t[d].tag;t[d].tag=;
        t[d*2].mx+=w;t[d*2+].mx+=w;
        t[d*2].tag+=w;t[d*2+].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)/;
        ins(d*2,l,mid,x,min(mid,y),z);
        ins(d*2+,mid+,r,max(x,mid+),y,z);
        t[d].mx=max(t[d*2].mx,t[d*2+].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)/;
        if (x<=mid) return find(d*2,l,mid,x);
        else return find(d*2+,mid+,r,x);
    }

    int get_max(int d,int l,int r,int x,int y)
    {
        if (x>y) return ;
        pushdown(d,l,r);
        if (l==x&&r==y) return t[d].mx;
        int mid=(l+r)/;
        return max(get_max(d*2,l,mid,x,min(y,mid)),get_max(d*2+,mid+,r,max(x,mid+),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 ;
        else return ;
    }

    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=;
        while (x)
        {
            splay(x);
            int y=findmn(t[x].r);
            if (y) Sig.ins(,,n,pos[y],mx[y],);
            t[x].r=p;
            y=findmn(p);
            if (y) Sig.ins(,,n,pos[y],mx[y],-);
            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]]+;size[x]=;
    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=;
    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=;i<n;i++)
    {
        int x,y;
        scanf("%d%d",&x,&y);
        addedge(x,y);
    }
    dfs1();
    dfs2(,);
    Sig.build(,,n);
    for (int i=;i<=m;i++)
    {
        int op;
        scanf("%d",&op);
        if (op==)
        {
            int x;
            scanf("%d",&x);
            lct.access(x);
        }
        else if (op==)
        {
            int x,y;
            scanf("%d%d",&x,&y);
            int lca=get_lca(x,y);
            printf("%d\n",Sig.find(,,n,pos[x])+Sig.find(,,n,pos[y])-*Sig.find(,,n,pos[lca])+);
        }
        else
        {
            int x;
            scanf("%d",&x);
            printf("%d\n",Sig.get_max(,,n,pos[x],mx[x]));
        }
    }
    return ;
}