Preface

感觉之前的题解写的都有一些乱，这里从头开始细讲一下这题的做法。

Solution

一开始拿到这类动态修改以及维护的树上问题，第一个就要考虑转化成序列问题来做。这题正是如此。

我们注意到在学习树链剖分的时候，提到了一个所谓的时间戳，就是对于所有的节点 $u$，我们在深度优先遍历它的时候，我们令第 $u$ 个节点被遍历到的顺序为 $\mathrm{dfn}_u$ 这就是时间戳。

然后这个 $\mathrm{dfn}$ 具有一个性质，就是对于一棵以 $x$ 为根的子树 $E_x$，我们记它的大小为 $\mathrm{siz}_x$，那么对于任意的 $u,v\in E$，若 $u\neq v$ 那么 $\mathrm{dfn}_u \neq \mathrm{dfn}_v$ 且 $\mathrm{dfn}_x\le \mathrm{dfn}_u, \mathrm{dfn}_v \le \mathrm{dfn}_x + \mathrm{siz}_x - 1$。这样每一个子树中的节点在 $\mathrm{dfn}$ 上是连续的，那么我们就可以把它拍扁成为一个序列。

那么接下来怎么做？

注意到 $1\le c\le 10^5$，很小，那么我们考虑对于颜色开一个 set 来维护。

具体地，对每一种颜色 $c$，我们都开一个 set，我们记为 $S_c$，其中 $S_c$ 的元素即为染上 $c$ 颜色的节点的 $\mathrm{dfn}$。

但直接朴素地把每一个询问都加入到 $S$ 中，空间时间都会爆炸，考虑优化。

每一次修改，对于一个以 $x$ 为根的子树 $E_x$，如果 $E_x$ 中的子节点在 $S_c$ 中出现过，我们就把它从 $S_c$ 中删掉，并且抹除该子节点为根的子树对颜色产生的所有贡献，最后再把 $\mathrm{dfn}_x$ 加入 $S_c$，并且在你维护的区间加区间修改的数据结构中把 $E_x$ 在 $\mathrm{dfn}$ 中连续的区间加 $1$ 也就维护了颜色的贡献。注意到每个点最多被删一次，一共只会删 $O(n)$ 次，加上 set 自带的 $O( \log n)$，复杂度 $O(n\log n)$ 可以接受。

区间加的实现用两个树状数组或线段树都可以，本篇给出了两份代码，供参考。

Code

如果用的 DevCpp5，编译参数记得加上 -std=c++14。存图用的 vector 常数大但好用。

Code1

线段树的实现，长度：2,561 byte。

#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
constexpr int N = 1e5 + 3;
int n, q, dfn[N], cnt, p[N], siz[N];
vector <int> e[N];
set <int> S[N];
namespace SegmentTree {
    i64 tr[N << 3], tag[N << 3];
    auto ls = [](int x) {return x << 1;};
    auto rs = [](int x) {return x << 1|1;};
    void push_up(int p) {tr[p] = tr[ls(p)] + tr[rs(p)];}
    void addtag (int p, int pl, int pr, i64 d) {
        tag[p] = tag[p] + d;
        tr[p] = (pr - pl + 1) * d + tr[p]; 
    }
    void push_down(int p, int pl, int pr) {
        if (tag[p]) {
            int mid = (pl + pr) >> 1;
            addtag(ls(p), pl, mid, tag[p]);
            addtag(rs(p), mid + 1, pr, tag[p]);
            tag[p] = 0;
        }
    }
    void update(int l, int r, i64 d, int p, int pl, int pr) {
        if (l <= pl && pr <= r) {addtag (p, pl, pr, d); return;}
        push_down(p, pl, pr);
        int mid = (pl + pr) >> 1;
        if (l <= mid) update(l, r, d, ls(p), pl, mid);
        if (r > mid)  update(l, r, d, rs(p), mid + 1, pr);
        push_up(p);
    }
    i64 query(int l, int r, int p, int pl, int pr) {
        push_down(p, pl, pr);
        if (l <= pl && pr <= r) {return tr[p];}
        int mid = (pl + pr) >> 1;
        long long res = 0;
        if (l <= mid) res += query(l, r, ls(p), pl, mid);
        if (r > mid)  res += query(l, r, rs(p), mid + 1, pr);
        return res;
    }
}
void dfs (int u, int fa) {
    dfn[u] = ++ cnt;
    p[dfn[u]] = u;
    siz[u] = 1;
    for (auto v : e[u]) {
        if (v == fa) continue;
        dfs (v, u); siz[u] += siz[v];
    }
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL), cout.tie(NULL);
    cin >> n >> q;
    for (int i = 1; i < n; i ++) {
        int u, v; cin >> u >> v;
        e[u].push_back(v), e[v].push_back(u);
    }
    dfs (1, 0);
    auto calEnd = [&](int u) {return dfn[u] + siz[u] - 1;};
    using namespace SegmentTree;
    for (int op, x, c; q --; ) {
        cin >> op >> x;
        if (op == 1) {
            cin >> c;
            auto it = S[c].upper_bound(dfn[x]);
            if (it != S[c].begin()) 
                if (calEnd(p[*prev(it)]) >= calEnd(x)) continue;
            while (it != S[c].end() && *it <= calEnd(x)) 
                update(*it, calEnd(p[*it]), -1, 1, 1, n), S[c].erase(it ++);
            S[c].insert(dfn[x]);
            update(dfn[x], calEnd(x), 1, 1, 1, n);
        }
        else cout << query(dfn[x], calEnd(x), 1, 1, n) << '\n';
    }
    return 0;
}

Code2

树状数组的实现，长度：1,844 byte。

#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
constexpr int N = 1e5 + 3;
int n, q, dfn[N], cnt, p[N], siz[N];
vector <int> e[N];
set <int> S[N];
template <size_t Siz>
class Fenwick_Tree {
private :
    i64 c[Siz]; int LowBit (int x) {return x & -x;}
public :
    void update (int x, i64 d) {
        for (; x <= n; x += LowBit(x)) c[x] += d;
    }
    i64 query (int x) {
        i64 res = 0;
        for (; x; x -= LowBit(x)) res += c[x];
        return res;
    }
};
Fenwick_Tree <N> Tr1, Tr2;
void dfs (int u, int fa) {
    dfn[u] = ++ cnt;
    p[dfn[u]] = u;
    siz[u] = 1;
    for (auto v : e[u]) {
        if (v == fa) continue;
        dfs (v, u); siz[u] += siz[v];
    }
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL), cout.tie(NULL);
    cin >> n >> q;
    for (int i = 1; i < n; i ++) {
        int u, v; cin >> u >> v;
        e[u].push_back(v), e[v].push_back(u);
    }
    dfs (1, 0);
    auto calEnd = [&](int u) {return dfn[u] + siz[u] - 1;};
    auto getAns = [&](int u) {
        return siz[u] * Tr1.query(dfn[u]) + 
               Tr2.query(calEnd(u)) - Tr2.query(dfn[u]);
    };
    auto change = [&](int u, i64 d) {
        Tr1.update(dfn[u], d);
        Tr1.update(calEnd(u) + 1, - d);
        Tr2.update(dfn[u], siz[u] * d);
    };
    for (int op, x, c; q --; ) {
        cin >> op >> x;
        if (op == 1) {
            cin >> c;
            auto it = S[c].upper_bound(dfn[x]);
            if (it != S[c].begin()) 
                if (calEnd(p[*prev(it)]) >= calEnd(x)) continue;
            while (it != S[c].end() && *it <= calEnd(x)) 
                change(p[*it], -1), S[c].erase(it ++);
            S[c].insert(dfn[x]), change(x, 1);
        }
        else cout << getAns(x) << '\n';
    }
    return 0;
}