Problem

Bob 有一棵 n 个点的有根树，其中 1 号点是根节点。Bob 在每个点上涂了颜色，并且每个点上的颜色不同。

定义一条路径的权值是：这条路径上的点（包括起点和终点）共有多少种不同的颜色。

Bob 可能会进行这几种操作：

1 x
把点 x 到根节点的路径上所有的点染上一种没有用过的新颜色。

2 x y
求 x 到 y 的路径的权值。

3 x
在以 x 为根的子树中选择一个点，使得这个点到根节点的路径权值最大，求最大权值。

Bob 一共会进行 m 次操作

Solution

emm 我并没做出来
我一开始想着怎么维护让一段区间的点的所有为 0 的儿子变成 1，然后这思路有各种问题
我果然还是太年轻

题解传送门：https://www.luogu.org/blog/newuser/solution-p3703

重点在于怎么快速进行操作 1，操作 2 / 3 的思路都差不多
树剖的做法是暴力更改？？恕我没看懂代码...

一种优美的做法是 LCT 的 Access 本质思想应用？
果然每种专题都有对本质思想的应用啊..

以及我一开始的查询其实是num[a]+num[b]-num[lca(a,b)]-num[fa[lca(a,b)]]类似这样的
然后这玩意是错的
所以为什么呢，请看下面的代码把 ww

Code

// Code by ajcxsu
// Problem: color on the tree

#include<bits/stdc++.h>
using namespace std;

template <typename T> inline void gn(T &x) {
    char ch=getchar();
    x=0;
    while(ch<'0' || ch>'9') ch=getchar();
    while(ch>='0' && ch<='9') x=x*10+ch-'0', ch=getchar();
} 

const int N=1e5+10, M=2e5+10;
int n,m;
int h[N], to[M], nexp[M], p=1;
inline void ins(int a,int b) {
    nexp[p]=h[a], h[a]=p, to[p]=b, p++;
}

namespace ST {
    #define ls x<<1
    #define rs x<<1|1
    int num[N*6], t[N*6];
    inline void pud(int x) {
        if(!t[x]) return;
        t[ls]+=t[x], t[rs]+=t[x];
        num[ls]+=t[x], num[rs]+=t[x];
        t[x]=0;
    }
    void updata(int x, int l, int r, int xl, int xr, int d) {
        pud(x);
        if(xl<=l && r<=xr) {
            num[x]+=d, t[x]+=d;
            return;
        }
        int mid=(l+r)>>1;
        if(xl<=mid) updata(ls, l, mid, xl, xr, d);
        if(xr>mid) updata(rs, mid+1, r, xl, xr, d); // 使得区间一定有交集，避免无谓的搜索 
        num[x]=max(num[ls], num[rs]);
    }
    int query(int x, int l, int r, int xl, int xr) {
        pud(x);
        if(xl<=l && r<=xr) return num[x];
        int mid=(l+r)>>1;
        if(xr<=mid) return query(ls, l, mid, xl, xr);
        else if(xl>mid) return query(rs, mid+1, r, xl, xr);
        else return max(query(ls, l, mid, xl, mid), query(rs, mid+1, r, mid+1, xr));
    }
}

int dep[N], son[N], fa[N], siz[N];
int dfn[N], top[N], idx;
int nl[N], nr[N];

struct Node *nil;
struct Node {
    int id;
    Node *f, *ch[2];
    Node (int id=0):id(id) {
        f=ch[0]=ch[1]=nil;
    }
    bool nroot() {
        return f->ch[0]==this || f->ch[1]==this;
    }
    int dir() {
        if(!nroot()) return -1;
        return f->ch[1]==this;
    }
} *nd[N];
void ini() {
    nil=new Node;
    nil->f=nil->ch[0]=nil->ch[1]=nil;
}

void rot(Node *x) {
    Node *y=x->f, *z=y->f;
    int d=x->dir();
    y->ch[d]=x->ch[!d];
    if(x->ch[!d]!=nil) x->ch[!d]->f=y;
    x->f=z;
    if(y->dir()!=-1) z->ch[y->dir()]=x;
    x->ch[!d]=y, y->f=x;
}

void splay(Node *x) {
    Node *y; 
    while(x->nroot()) {
        y=x->f;
        if(!y->nroot()) rot(x);
        else if(y->dir() == x->dir()) rot(y), rot(x);
        else rot(x), rot(x);
    }
}

Node *find(Node *r) {
    while(r->ch[0]!=nil) r=r->ch[0];
    return r;
}

void access(Node *x) {
    Node *y=nil;
    int a;
    while(x!=nil) {
        splay(x);
        if(x->ch[1]!=nil) {
            a=find(x->ch[1])->id;
            ST::updata(1, 1, n, nl[a], nr[a], 1);
        }
        x->ch[1]=y;
        if(y!=nil) {
            a=find(y)->id;
            ST::updata(1, 1, n, nl[a], nr[a], -1);
        }
        y=x, x=x->f;
    }
}

void dfs1(int x, int k) {
    dep[x]=k, siz[x]=1;
    for(int u=h[x];u;u=nexp[u])
        if(!dep[to[u]]) {
            fa[to[u]]=x, nd[to[u]]->f=nd[x], dfs1(to[u], k+1);
            siz[x]+=siz[to[u]];
            if(siz[to[u]]>siz[son[x]]) son[x]=to[u];
        }
}
void dfs2(int x, int t) {
    nl[x]=dfn[x]=++idx;
    ST::updata(1, 1, n, dfn[x], dfn[x], dep[x]);
    top[x]=t;
    if(son[x]) dfs2(son[x], t);
    for(int u=h[x];u;u=nexp[u])
        if(!dfn[to[u]]) dfs2(to[u], to[u]);
    nr[x]=idx;
}
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]];
    }
    if(dep[x]>dep[y]) return y;
    return x; 
}

int main() {
    ini();
    gn(n), gn(m);
    int u,v;
    for(int i=1;i<n;i++) gn(u), gn(v), ins(u,v), ins(v,u);
    for(int i=1;i<=n;i++) nd[i]=new Node(i);
    dfs1(1,1), dfs2(1,1);
    int a,b,c,d;
    while(m--) {
        gn(a), gn(b);
        if(a==1) access(nd[b]);
        else if(a==2) {
            gn(c), d=lca(b,c);
            printf("%d\n", ST::query(1,1,n,dfn[b],dfn[b])+ST::query(1,1,n,dfn[c],dfn[c])
                            -2*ST::query(1,1,n,dfn[d],dfn[d])+1); // 由于两个都减去了d所在的splay，因此得把它加回来
            // 由于fa[d]和d有可能是在同一个splay，所以仍然导致少算上一个splay 
        }
        else if(a==3) printf("%d\n", ST::query(1,1,n,nl[b],nr[b]));
    }
    return 0;
}

本文链接：https://pst.iorinn.moe/archives/sol-luogu-3703.html
许可： https://pst.iorinn.moe/license.html
若无特别说明，博客内的文章默认将采用 CC BY 4.0 许可协议 进行许可☆