SDOI2017树点染色

题目链接

发现1操作很像lct中的access，然后它每次染的又是一个新颜色，因此同一个颜色就在同一颗splay里了，且一个点到根的权值val[i]也就是到根路径上虚边的个数，然后看access时会对哪些点的val[i]产生影响。

以下的原儿子表示原来与x在同一颗splay中的儿子 (注意不是splay中x的儿子，是原树中x的儿子，即splay中x的后继)。

当x断开与它原儿子所在splay的连接时，原儿子的子树val都要+1，接上的新儿子的splay，新儿子所在子树val要-1。

对于2操作，相当于统计x~y路径上虚边个数+1，val[x]+val[y]-2*val[lca]+1即是。

对于3操作在子树中找个最大的val即可。

val的话可以用线段树维护。

#include<cstdio>

#include<cstdlib>

#include<cstring>

#include<iostream>

#include<vector>

#include<algorithm>

#include<queue>

#include<cmath>

#include<stack>

#include<map>

#define P puts("lala")

#define cp cerr<<"lala"<<endl

#define ln putchar('\n')

#define sp putchar(' ')

#define pb push_back

#define fi first

#define se second

#define mkp make_pair

using namespace std;

typedef pair<int,int> pii;

inline void read(int &re)

{

    char ch=getchar();int g=1;

    while(ch<'0'||ch>'9') {if(ch=='-')g=-1;ch=getchar();}

    re=0;

    while(ch<='9'&&ch>='0') re=(re<<1)+(re<<3)+(ch^48),ch=getchar();

    re*=g;

}

typedef long long ll;

inline void read(ll &re)

{

    char ch=getchar();ll g=1;

    while(ch<'0'||ch>'9') {if(ch=='-')g=-1;ch=getchar();}

    re=0;

    while(ch<='9'&&ch>='0') re=(re<<1)+(re<<3)+ch-48ll,ch=getchar();

    re*=g;

}

const int N=100050;

int maxv[N<<2],add[N<<2],fa[N],ch[N][2];

int siz[N],dfn[N],tot=0,is[N],f[N][21],n,dep[N];

int head[N],cnt=0;

struct node

{

    int to,next;

}e[N<<1];

inline void add_edge(int x,int y)

{

    e[++cnt]=(node){y,head[x]};head[x]=cnt;

    e[++cnt]=(node){x,head[y]};head[y]=cnt;

}

void build(int o,int l,int r)

{

    if(l==r) {maxv[o]=dep[is[l]];return ;}

    int mid=l+r>>1;

    build(o<<1,l,mid); build(o<<1|1,mid+1,r);

    maxv[o]=max(maxv[o<<1],maxv[o<<1|1]);

}

void pushdown(int o)

{

    if(add[o])

    {

        add[o<<1]+=add[o]; add[o<<1|1]+=add[o];

        maxv[o<<1]+=add[o]; maxv[o<<1|1]+=add[o];

        add[o]=0;

    }

}

void update(int o,int l,int r,int x,int y,int k) //add k

{

    if(x<=l&&r<=y) {add[o]+=k;maxv[o]+=k;return ;}

    pushdown(o);

    int mid=l+r>>1;

    if(x<=mid) update(o<<1,l,mid,x,y,k);

    if(y>mid) update(o<<1|1,mid+1,r,x,y,k);

    maxv[o]=max(maxv[o<<1],maxv[o<<1|1]);

}

int query(int o,int l,int r,int x,int y)

{

    if(x<=l&&r<=y) return maxv[o];

    pushdown(o);

    int mid=l+r>>1,ans=0;

    if(x<=mid) ans=query(o<<1,l,mid,x,y);

    if(y>mid) ans=max(ans,query(o<<1|1,mid+1,r,x,y));

    return ans;

}

inline bool ge(int x) {return ch[fa[x]][1]==x;}

inline bool isroot(int x) {return ch[fa[x]][1]!=x&&ch[fa[x]][0]!=x;}

inline void rotate(int x)

{

    int f=fa[x],g=fa[f],wh=ge(x);

    if(!isroot(f)) ch[g][ch[g][1]==f]=x;

    ch[f][wh]=ch[x][wh^1]; fa[ch[f][wh]]=f;

    ch[x][wh^1]=f; fa[f]=x;

    fa[x]=g;

}

void splay(int x)

{

    for(int f;(f=fa[x])&&!isroot(x);rotate(x))

        if(!isroot(f)) rotate(ge(x)==ge(f)?f:x);

}

int nex(int x)

{

    x=ch[x][1];

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

    return x;

}

void access(int x)

{

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

    {

        splay(x);

        if(ch[x][1])

        {

            int y=nex(x);

            update(1,1,n,dfn[y],dfn[y]+siz[y]-1,1);

        }

        ch[x][1]=t;

        if(ch[x][1])

        {

            int y=nex(x);

            update(1,1,n,dfn[y],dfn[y]+siz[y]-1,-1);

        }

    }

}

void dfs(int u,int dad,int d)

{

    fa[u]=dad; f[u][0]=dad;

    dfn[u]=++tot; is[tot]=u;

    siz[u]=1; dep[u]=d;

    for(int i=head[u];i;i=e[i].next)

    {

        int v=e[i].to;

        if(v==dad) continue;

        dfs(v,u,d+1);

        siz[u]+=siz[v];

    }

}

int lca(int x,int y)

{

    if(dep[x]<dep[y]) swap(x,y);

    int d=dep[x]-dep[y];

    for(int i=19;i>=0;--i) if(d&(1<<i)) x=f[x][i];

    if(x==y) return x;

    for(int i=19;i>=0;--i) if(f[x][i]!=f[y][i]) x=f[x][i],y=f[y][i];

    return f[x][0];

}

int ask(int x,int y)

{

    int o=lca(x,y);

    return query(1,1,n,dfn[x],dfn[x])+query(1,1,n,dfn[y],dfn[y])

    -query(1,1,n,dfn[o],dfn[o])*2;

}

int main()

{

#ifndef ONLINE_JUDGE

    freopen("1.in","r",stdin);freopen("1.out","w",stdout);

#endif

    int i,j,opt,T;

    read(n);read(T);

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

    {

        int x,y;read(x);read(y);

        add_edge(x,y);

    }

    dfs(1,0,0);

    for(j=1;j<=19;++j) for(i=1;i<=n;++i) f[i][j]=f[f[i][j-1]][j-1];

    build(1,1,n);

    for(int cas=1;cas<=T;++cas)

    {

        read(opt);

        if(opt==1)

        {

            int x;read(x);

            access(x);

        }

        else if(opt==2)

        {

            int x,y;read(x);read(y);

            printf("%d\n",ask(x,y)+1);

        }

        else

        {

            int x;read(x);

            printf("%d\n",query(1,1,n,dfn[x],dfn[x]+siz[x]-1)+1);

        }

    }

    return 0;

}

/*

*/

SDOI2017树点染色的相关教程结束。