Luogu

LOJ

分析

因为每次都是把一条到根的路径染一种不同的颜色,所以颜色种数实际上就等于颜色段数。

考虑 $1$ 操作时发生了什么,可以发现实际上把一些点的答案减了 $1$ ,另一些点的答案加了 $1$ 。

进一步可以发现,$-1$ 的部分实际上是 access 之前的右儿子,$+1$ 的部分实际上是 access 时候的右儿子。

那么写一个 LCT 就好了。

$2$ 操作可以利用树上差分那一套求,$3$ 操作相当于子树求 $\max$ 。

所以只需要写一个树剖、一个支持区间修改区间取 $\max$ 的线段树,以及一个只有 access 的 LCT 就好了。

讲的可能不是很清楚,可以画图理解一下。

代码

// ===================================
//   author: M_sea
//   website: http://m-sea-blog.com/
// ===================================
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <queue>
#define re register
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=200000+10;

int n,Q;

struct edge { int v,nxt; } e[N<<1];
int head[N];
inline void addEdge(int u,int v) {
    static int cnt=0;
    e[++cnt]=(edge){v,head[u]},head[u]=cnt;
}

int fa[N],dep[N],sz[N],hson[N],top[N];
int dfn[N],low[N],id[N],tim=0;
inline void dfs1(int u,int f) {
    fa[u]=f,dep[u]=dep[f]+1,sz[u]=1;
    for (re int i=head[u];i;i=e[i].nxt) {
        int v=e[i].v; if (v==f) continue;
        dfs1(v,u),sz[u]+=sz[v];
        if (sz[v]>sz[hson[u]]) hson[u]=v;
    }
}
inline void dfs2(int u,int anc) {
    dfn[u]=++tim,id[tim]=u,top[u]=anc;
    if (hson[u]) dfs2(hson[u],anc);
    for (re int i=head[u];i;i=e[i].nxt)
        if (e[i].v!=fa[u]&&e[i].v!=hson[u]) dfs2(e[i].v,e[i].v);
    low[u]=tim;
}
inline int getLCA(int u,int v) {
    while (top[u]!=top[v]) {
        if (dep[top[u]]<dep[top[v]]) swap(u,v);
        u=fa[top[u]];
    }
    if (dep[u]<dep[v]) swap(u,v);
    return v;
}

struct Segment_Tree {
#define ls (o<<1)
#define rs (o<<1|1)
    int addv[N<<2],maxv[N<<2];
    inline void pushup(int o) { maxv[o]=max(maxv[ls],maxv[rs]); }
    inline void pushdown(int o) {
        if (addv[o]) {
            addv[ls]+=addv[o],addv[rs]+=addv[o];
            maxv[ls]+=addv[o],maxv[rs]+=addv[o];
            addv[o]=0;
        }
    }
    inline void build(int o,int l,int r) {
        if (l==r) { maxv[o]=dep[id[l]]; return; }
        int mid=(l+r)>>1;
        build(ls,l,mid),build(rs,mid+1,r);
        pushup(o);
    }
    inline void modify(int o,int l,int r,int ql,int qr,int v) {
        if (ql<=l&&r<=qr) { addv[o]+=v,maxv[o]+=v; return; }
        int mid=(l+r)>>1; pushdown(o);
        if (ql<=mid) modify(ls,l,mid,ql,qr,v);
        if (qr>mid) modify(rs,mid+1,r,ql,qr,v);
        pushup(o);
        
    }
    inline int query(int o,int l,int r,int ql,int qr) {
        if (ql<=l&&r<=qr) return maxv[o];
        int mid=(l+r)>>1,res=0; pushdown(o);
        if (ql<=mid) res=max(res,query(ls,l,mid,ql,qr));
        if (qr>mid) res=max(res,query(rs,mid+1,r,ql,qr));
        pushup(o); return res;
    }
#undef ls
#undef rs
} SGT;

struct Link_Cut_Tree {
    int fa[N],ch[N][2];
    inline int nroot(int x) { return ch[fa[x]][0]==x||ch[fa[x]][1]==x; }
    inline void rotate(int x){
        int y=fa[x],z=fa[y],k=(x==ch[y][1]),w=ch[x][!k];
        if (nroot(y)) ch[z][ch[z][1]==y]=x;
        ch[x][!k]=y,ch[y][k]=w;
        if (w) fa[w]=y; fa[y]=x,fa[x]=z;
    }
    inline void splay(int x) {
        while (nroot(x)) {
            int y=fa[x],z=fa[y];
            if (nroot(y)) rotate((ch[y][0]==x)^(ch[z][0]==y)?x:y);
            rotate(x);
        }
    }
    inline int findroot(int x) {
        while (ch[x][0]) x=ch[x][0];
        return x;
    }
    inline void access(int x) {
        for (re int y=0;x;x=fa[y=x]) {
            splay(x);
            if (ch[x][1]) {
                int t=findroot(ch[x][1]);
                SGT.modify(1,1,n,dfn[t],low[t],1);
            }
            ch[x][1]=y;
            if (ch[x][1]) {
                int t=findroot(ch[x][1]);
                SGT.modify(1,1,n,dfn[t],low[t],-1);
            }
        }
    }
} LCT;

int main() {
    n=read(),Q=read();
    for (re int i=1;i<n;++i) {
        int u=read(),v=read();
        addEdge(u,v),addEdge(v,u);
    }
    dfs1(1,0),dfs2(1,1);
    for (re int i=1;i<=n;++i) LCT.fa[i]=fa[i];
    SGT.build(1,1,n);
    while (Q--) {
        int op=read();
        if (op==1) LCT.access(read());
        else if (op==2) {
            int u=read(),v=read(),t=getLCA(u,v),ans=1;
            ans+=SGT.query(1,1,n,dfn[u],dfn[u]);
            ans+=SGT.query(1,1,n,dfn[v],dfn[v]);
            ans-=SGT.query(1,1,n,dfn[t],dfn[t])<<1;
            printf("%d\n",ans);
        }
        else {
            int u=read();
            printf("%d\n",SGT.query(1,1,n,dfn[u],low[u]));
        }
    }
    return 0;
}
最后修改:2019 年 09 月 27 日 01 : 37 PM