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

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

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

$1 \ x$ ，把点 $x$ 到根节点的路径上的所有的点染上一种没有用过的新颜色；
$2 \ x \ y$ ，求 $x$ 到 $y$ 的路径的权值；
$3 \ x$ ，在以 $x$ 为根的子树中选择一个点，使得这个点到根节点的路径权值最大，求最大权值。

Bob 一共会进行 $m$ 次操作。

题解

明显地，操作 $1$ 对应的是 LCT 里的 access 操作，由于每次染上的颜色一定是一个没有出现过的颜色，所以说有两个比较明显的结论：

LCT 中每条实路径上的颜色是相同的。
一个节点到根路径上颜色种类的数量等于它到根路径上虚边的个数。

这样，用线段树维护节点到根路径上的颜色种类数，access 时每次虚实边转换时，虚边变成实边的，子树中答案集体减一，实边变成虚边的，子树中答案集体加一。

对于操作 $3$ ，直接线段树查找子树最大就可以了。

对于操作 $2$ ，简单的 yy 一下以后可以发现，两个节点的颜色不可能同时和它们的 LCA 相同，所以 LCA 的颜色对答案的贡献一定是 $1$ ，这样，我们就把两个点到根路径上的颜色数各自减去 LCA 到根路径上的颜色数，然后再加上 LCA 贡献的 $1$ 即可。

代码

专业写挂线段树。

#include <cstdio>
#include <cstring>
#include <climits>
#include <stack>
#include <algorithm>
const int MAX_N = 1e5;
struct Node;
struct Edge;
struct Node {
    Edge *e;
    Node *fa, *top, *maxc;
    int dep, size, min, max;
    bool vis;
} N[MAX_N + 1];
struct Edge {
    Node *to;
    Edge *ne;
    
    Edge(Node *fr, Node *to) : to(to), ne(fr->e) {}
};
inline void addEdge(int fr, int to) {
    N[fr].e = new Edge(&N[fr], &N[to]);
    N[to].e = new Edge(&N[to], &N[fr]);
}
int n, m;
inline void split() {
    std::stack<Node *> s;
    s.push(&N[1]);
    N[1].dep = 1;
    while (!s.empty()) {
        Node *v = s.top();
        if (!v->vis) {
            v->vis = true;
            for (Edge *e = v->e; e; e = e->ne) {
                if (e->to != v->fa) {
                    e->to->fa = v;
                    e->to->dep = v->dep + 1;
                    s.push(e->to);
                }
            }
        } else {
            v->size = 1;
            
            for (Edge *e = v->e; e; e = e->ne) {
                if (e->to->fa == v) {
                    v->size += e->to->size;
                    if (!v->maxc || v->maxc->size < e->to->size) v->maxc = e->to;
                }
            }
            s.pop();
        }
    }
    for (int i = 1; i <= n; i++) N[i].vis = false;
    int ts = 0;
    s.push(&N[1]);
    while (!s.empty()) {
        Node *v = s.top();
        if (!v->vis) {
            v->vis = true;
            v->min = ++ts;
            if (!v->fa || v != v->fa->maxc) v->top = v;
            else v->top = v->fa->top;
            for (Edge *e = v->e; e; e = e->ne) {
                if (e->to->fa == v && e->to != v->maxc) {
                    s.push(e->to);
                }
            }
            if (v->maxc) s.push(v->maxc);
        } else {
            v->max = ts;
            s.pop();
        }
    }
}
int a[MAX_N + 1];
struct Segt {
    int l, r;
    Segt *lc, *rc;
    int max;
    int tag;
    Segt(int l, int r, Segt *lc, Segt *rc) : l(l), r(r), lc(lc), rc(rc), max(std::max(lc->max, rc->max)), tag(0) {}
    Segt(int l, int r, Segt *lc, Segt *rc, int max) : l(l), r(r), lc(lc), rc(rc), max(max), tag(0) {}
    void maintain() {
        max = std::max(lc->max, rc->max);
    }
    void add(int x) {
        max += x;
        tag += x;
    }
    void pushDown() {
        if (tag) {
            lc->add(tag);
            rc->add(tag);
            tag = 0;
        }
    }
    void modify(int l, int r, int val) {
        if (l > this->r || r < this->l) return;
        else if (l <= this->l && r >= this->r) add(val);
        else pushDown(), lc->modify(l, r, val), rc->modify(l, r, val), maintain();
    }
    int query(int pos) {
        if (l == r) return max;
        else {
            pushDown();
            int mid = l + (r - l) / 2;
            if (pos <= mid) return lc->query(pos);
            else if (pos > mid) return rc->query(pos);
        }
    }
    int query(int l, int r) {
        if (l > this->r || r < this->l) return 0;
        else if (l <= this->l && r >= this->r) return max;
        else return pushDown(), std::max(lc->query(l, r), rc->query(l, r));
    }
    static Segt *build(int l, int r) {
        if (l == r) return new Segt(l, r, NULL, NULL, N[a[l]].dep);
        else {
            int mid = l + (r - l) / 2;
            return new Segt(l, r, build(l, mid), build(mid + 1, r));
        }
    }
} *segt;
struct LinkCutTree {
    struct Node {
        Node *c[2], *fa, *pathFa, *min;
        int begin, end;
        Node() : min(this) {}
        void maintain() {
            if (c[0]) min = c[0]->min;
            else min = this;
        }
        
        int relation() {
            return this == fa->c[1];
        }
        void rotate() {
            std::swap(pathFa, fa->pathFa);
            Node *old = fa;
            int x = relation();
            fa = old->fa;
            if (old->fa) old->fa->c[old->relation()] = this;
            old->c[x] = c[x ^ 1];
            if (c[x ^ 1]) c[x ^ 1]->fa = old;
            c[x ^ 1] = old;
            old->fa = this;
            old->maintain(), maintain();
        }
        void splay() {
            while (fa) {
                if (!fa->fa) rotate();
                else if (fa->relation() == relation()) fa->rotate(), rotate();
                else rotate(), rotate();
            }
        }
        void expose() {
            splay();
            if (c[1]) {
                segt->modify(c[1]->min->begin, c[1]->min->end, +1);
                std::swap(c[1]->fa, c[1]->pathFa);
                c[1] = NULL;
            }
        }
        bool splice() {
            splay();
            if (!pathFa) return false;
            segt->modify(this->min->begin, this->min->end, -1);
            pathFa->expose();
            pathFa->c[1] = this;
            std::swap(fa, pathFa);
            return true;
        }
        void access() {
            expose();
            while (splice());
        }
    } N[MAX_N + 1];
    void link(int x, int fa) {
        Node *v = &N[x], *par = &N[fa];
        v->pathFa = par;
    }
    void init() {
        for (int i = 1; i <= n; i++) {
            N[i].begin = ::N[i].min, N[i].end = ::N[i].max;
            if (::N[i].fa) link(i, static_cast<int>(::N[i].fa - ::N));
        }
    }
    void change(int x) {
        Node *v = &N[x];
        v->access();
    }
} lct;
inline void change(int x) {
    lct.change(x);
}
inline int queryMax(int x) {
    return segt->query(N[x].min, N[x].max);
}
inline Node *lca(Node *u, Node *v) {
    while (u->top != v->top) {
        if (u->top->dep < v->top->dep) std::swap(u, v);
        u = u->top->fa;
    }
    if (u->dep < v->dep) return u;
    else return v;
}
inline int query(int a, int b) {
    Node *u = &N[a], *v = &N[b];
    Node *p = lca(u, v);
    return segt->query(u->min) + segt->query(v->min) - segt->query(p->min) * 2 + 1;
}
int main() {
//	freopen("paint.in", "r", stdin);
//	freopen("paint.out", "w", stdout);
    scanf("%d %d", &n, &m);
    for (int i = 1; i < n; i++) {
        int u, v;
        scanf("%d %d", &u, &v);
        addEdge(u, v);
    }
    split();
    lct.init();
    for (int i = 1; i <= n; i++) a[N[i].min] = i;
    segt = Segt::build(1, n);
    for (int i = 1; i <= m; i++) {
        int cmd, x, y;
        scanf("%d", &cmd);
        
        if (cmd == 1) {
            scanf("%d", &x);
            change(x);
        } else if (cmd == 2) {
            scanf("%d %d", &x, &y);
            printf("%d\n", query(x, y));
        } else if (cmd == 3) {
            scanf("%d", &x);
            printf("%d\n", queryMax(x));
        } else throw "%%%Menci";
    }
    fclose(stdin), fclose(stdout);
    return 0;
}

「SDOI2017」树点涂色 - LCT，线段树

Contents

题解

代码