正题

题目链接:https://www.luogu.com.cn/problem/P3703

题目大意

\(n\)个点的一棵树开始所有点有不同的颜色，\(m\)次操作

将根节点到\(x\)节点的路径上染上一种新的颜色
询问一条路径的不同颜色个数
询问一个节点的子树中的一个\(x\)使得\(x\)到根节点的颜色最多。

解题思路

操作\(1\)和\(LCT\)的\(access\)操作很相似。相同颜色之间就是实边，不同颜色之间就是虚边。

操作\(2\)就是之间\(p_x+p_y-2p_{LCA}+1\)就好了，但是考虑到操作\(3\)，所以维护一个\(dfn\)序和线段树就可以查询子树最大值了。

之后维护一个\(LCT\)，在\(access\)操作切换虚实边的时候修改一下线段树就好了，并且需要注意我们不能直接拿\(Splay\)的根的子树，要找到实际的树中的根，所以\(Splay\)一直往左就好了。

好像还有树链剖分的做法，线段树查询的时候维护一下末尾颜色好像就可以了，这里不多讲（我也不会）

时间复杂度\(O(n\log^2 n)\)

code

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

const int N=1e5+10;

struct node{

    int to,next;

}a[N<<1];

int n,m,cnt,tot,ls[N],rfn[N],ed[N],fa[N];

int dep[N],son[N],siz[N],top[N];

struct SegTree{

    int w[N<<2],lazy[N<<2];

    void Downdata(int x){

        if(!lazy[x])return;

        w[x*2]+=lazy[x];lazy[x*2]+=lazy[x];

        w[x*2+1]+=lazy[x];lazy[x*2+1]+=lazy[x];

        lazy[x]=0;return;

    }

    void Change(int x,int L,int R,int l,int r,int val){

        if(L==l&&R==r){w[x]+=val;lazy[x]+=val;return;}

        int mid=(L+R)>>1;Downdata(x);

        if(r<=mid)Change(x*2,L,mid,l,r,val);

        else if(l>mid)Change(x*2+1,mid+1,R,l,r,val);

        else Change(x*2,L,mid,l,mid,val),Change(x*2+1,mid+1,R,mid+1,r,val);

        w[x]=max(w[x*2],w[x*2+1]);return;

    }

    int Ask(int x,int L,int R,int l,int r){

        if(L==l&&R==r)return w[x];

        int mid=(L+R)>>1;Downdata(x);

        if(r<=mid)return Ask(x*2,L,mid,l,r);

        if(l>mid)return Ask(x*2+1,mid+1,R,l,r);

        return max(Ask(x*2,L,mid,l,mid),Ask(x*2+1,mid+1,R,mid+1,r));

    }

}Tr;

struct LinkCutTree{

    int t[N][2],fa[N];

    bool Nroot(int x)

    {return fa[x]&&(t[fa[x]][0]==x||t[fa[x]][1]==x);}

    bool Direct(int x)

    {return t[fa[x]][1]==x;}

    void Rotate(int x){

        int y=fa[x],z=fa[y];

        int xs=Direct(x),ys=Direct(y);

        int w=t[x][xs^1];

        if(Nroot(y))t[z][ys]=x;

        t[x][xs^1]=y;t[y][xs]=w;

        if(w)fa[w]=y;fa[y]=x;fa[x]=z;

        return;

    }

    void Splay(int x){

        while(Nroot(x)){

            int y=fa[x];

            if(!Nroot(y))Rotate(x);

            else if(Direct(x)==Direct(y))

                Rotate(y),Rotate(x);

            else Rotate(x),Rotate(x);

        }

        return;

    }

    int FindRoot(int x){

        while(t[x][0])x=t[x][0];

        return x;

    }

    void Access(int x){

        for(int y=0;x;y=x,x=fa[x]){

            Splay(x);int z=t[x][1];

            if(z)z=FindRoot(z),Tr.Change(1,1,n,rfn[z],ed[z],1);

            if(y)z=FindRoot(y),Tr.Change(1,1,n,rfn[z],ed[z],-1);

            t[x][1]=y;

        }

        return;

    }

}T;

void addl(int x,int y){

    a[++tot].to=y;

    a[tot].next=ls[x];

    ls[x]=tot;return;

}

void dfs1(int x){

    siz[x]=1;rfn[x]=++cnt;

    dep[x]=dep[fa[x]]+1;T.fa[x]=fa[x];

    Tr.Change(1,1,n,cnt,cnt,dep[x]);

    for(int i=ls[x];i;i=a[i].next){

        int y=a[i].to;

        if(y==fa[x])continue;

        fa[y]=x;dfs1(y);siz[x]+=siz[y];

        if(siz[y]>siz[son[x]])son[x]=y;

    }

    ed[x]=cnt;

}

void dfs2(int x){

    if(son[x]){

        top[son[x]]=top[x];

        dfs2(son[x]);

    }

    for(int i=ls[x];i;i=a[i].next){

        int y=a[i].to;

        if(y==fa[x]||y==son[x])continue;

        top[y]=y;dfs2(y);

    }

    return;

}

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

    }

    return dep[x]<dep[y]?x:y;

}

int main()

{

    // freopen("paint1.in","r",stdin);

    scanf("%d%d",&n,&m);

    for(int i=1;i<n;i++){

        int x,y;

        scanf("%d%d",&x,&y);

        addl(x,y);addl(y,x);

    }

    dfs1(1);dfs2(1);

    while(m--){

        int op,x,y;

        scanf("%d%d",&op,&x);

        if(op==1)T.Access(x);

        else if(op==2){

            scanf("%d",&y);

            int lca=LCA(x,y);

            int p1=Tr.Ask(1,1,n,rfn[x],rfn[x]);

            int p2=Tr.Ask(1,1,n,rfn[y],rfn[y]);

            int p3=Tr.Ask(1,1,n,rfn[lca],rfn[lca]);

            printf("%d\n",p1+p2-p3*2+1);

        }

        else printf("%d\n",Tr.Ask(1,1,n,rfn[x],ed[x]));

    }

    return 0;

}

巴特西

P3703-[SDOI2017]树点涂色【LCT,线段树】

正题

题目大意

解题思路

code

最新文章

热门文章