P3703 [SDOI2017] 树点涂色

· · 个人记录

神。

操作 1

这个操作很像 access。LCT 上每一个 Splay 维护一个自下而上的链。而同一个颜色的链也是如此。每一个 Splay 维护一种颜色。操作 1 相当于 access 操作。

操作 2/3

查询链之间的信息，无法用 LCT 来维护了，因为 LCT 已经维护了同一种颜色的集合。考虑到操作三要查询子树信息，这用 LCT 无法做到。只能是先维护好每个点到根节点的权值 f_u，然后区间查询最大值。先不说怎么维护，那么操作二就可以变成树上差分，因为不可能有岔路同一种颜色，答案为 f_u+f_v-2f_{lca(u,v)}+1。

那么只需要维护好这个 f_u 即可。观察 LCT，f_u 等于根节点链上轻边个数+1。那么我们维护好每个点到根节点的轻边个数即可，只需要在 access 里更改，相当于子树修改，因为操作三还要区间查询，用线段树即可。注意修改的时候需要找到子树的根节点，不能直接用右儿子，需要在 splay 树上查询深度最小的点，不断跳左儿子即可。

#include<bits/stdc++.h>
#define Iv inline void
typedef long long LL;
using namespace std;
const int N=1e5;
int n,Q,dep[N+5],fa[N+5][19],dfn[N+5],siz[N+5],tot,b[N+5]; vector<int> e[N+5];
void dfs(int u,int Fa){
    fa[u][0]=Fa; dep[u]=dep[Fa]+1; b[dfn[u]=++tot]=u; siz[u]=1;
    for(int i=1;i<17;i++) fa[u][i]=fa[ fa[u][i-1] ][i-1];
    for(int v:e[u]){
        if(v==Fa) continue;
        dfs(v,u); siz[u]+=siz[v];
    }
}
int LCA(int u,int v){
    if(dep[u]<dep[v]) swap(u,v);
    for(int i=16;i>=0;i--)
        if(dep[fa[u][i]]>=dep[v]) u=fa[u][i];
    if(u==v) return u;
    for(int i=16;i>=0;i--)
        if(fa[u][i]!=fa[v][i]) u=fa[u][i],v=fa[v][i];
    return fa[u][0];
}
namespace subTree{
    struct tnode{
        int mx,tg;
        void addt(int x){
            mx+=x; tg+=x;
        }
    } tr[4*N+5];
    Iv pushdn(int p){
        if(tr[p].tg){
            tr[p<<1].addt(tr[p].tg); tr[p<<1|1].addt(tr[p].tg);
            tr[p].tg=0;
        }
    }
    Iv pushup(int p){
        tr[p].mx=max(tr[p<<1].mx,tr[p<<1|1].mx);
    }
    Iv build(int p,int L,int R){
        if(L==R) {tr[p].mx=dep[b[L]]; return ;}
        int mid=(L+R)/2;
        build(p<<1,L,mid); build(p<<1|1,mid+1,R);
        pushup(p);
    }
    Iv Modify(int p,int L,int R,int lt,int rt,int x){
        if(L>rt || R<lt) return ;
        if(L>=lt && R<=rt) { tr[p].addt(x); return ;}
        int mid=(L+R)/2; pushdn(p);
        Modify(p<<1,L,mid,lt,rt,x); Modify(p<<1|1,mid+1,R,lt,rt,x);
        pushup(p);
    }
    int Query(int p,int L,int R,int lt,int rt){
        if(L>rt || R<lt) return 0;
        if(L>=lt && R<=rt) return tr[p].mx;
        int mid=(L+R)/2; pushdn(p);
        return max(Query(p<<1,L,mid,lt,rt),Query(p<<1|1,mid+1,R,lt,rt));
    }
    int Aseg(int p) {return Query(1,1,n,dfn[p],dfn[p]);}
    Iv Mseg(int p,int x) {  Modify(1,1,n,dfn[p],dfn[p]+siz[p]-1,x);}
}
using namespace subTree;
namespace LCT{
struct node{
    int c[2],fa;
} tr[N+5]; 
inline bool gd(int p) { return tr[tr[p].fa].c[1]==p; }
inline bool isroot(int p) { return !tr[p].fa || tr[tr[p].fa].c[gd(p)]!=p;}
Iv cnet(int u,int d,int v){ tr[u].c[d]=v; tr[v].fa=u; }
Iv rot(int p){
    int fp=tr[p].fa,gp=tr[fp].fa,d=gd(p);
    if(isroot(fp)) tr[p].fa=gp;
    else cnet(gp,gd(fp),p);
    cnet(fp,d,tr[p].c[!d]); cnet(p,!d,fp);
}
Iv splay(int p){
    while(!isroot(p)){
        int fp=tr[p].fa;
        if(!isroot(fp)){
            if(gd(p)==gd(fp)) rot(fp);
            else rot(p);
        }
        rot(p);
    }
}
int findrt(int p){
    while(tr[p].c[0]) p=tr[p].c[0];
    return p;
}
Iv access(int p){
    for(int x=0;p;p=tr[x=p].fa){
        splay(p); int y=tr[p].c[1]; tr[p].c[1]=x;
        if(y) Mseg(findrt(y),1);
        if(x) Mseg(findrt(x),-1);
    }
}
}
using namespace LCT;
int main(){
    scanf("%d%d",&n,&Q);
    for(int i=1,u,v;i<n;i++){
        scanf("%d%d",&u,&v);
        e[u].push_back(v); e[v].push_back(u);
    }
    dfs(1,0); build(1,1,n);
    for(int i=1;i<=n;i++) LCT::tr[i].fa=fa[i][0];
    while(Q--){
        int op,u,v; scanf("%d%d",&op,&u);
        if(op==1) access(u);
        else if(op==2){
            scanf("%d",&v); int lc=LCA(u,v);
            printf("%d\n",Aseg(u)+Aseg(v)-2*Aseg(lc)+1);
        }
        else printf("%d\n",Query(1,1,n,dfn[u],dfn[u]+siz[u]-1));
    }
    return 0;
}