Lời giải

Trước hết, ta sẽ dfs cây với bí ngô gốc là ~1~, gọi ~st_x~ là thời gian thăm bí ngô ~x~, ~en_x~ là bí ngô cuối cùng được thăm trong cây bí ngô gốc ~x~. Như vậy, cây bí ngô gốc ~x~ sẽ được biểu diễn trong đoạn ~[st_x, en_x]~.

Gọi ~sub_x~ là số bí ngô trong cây bí ngô gốc ~x~.

Với mỗi phụ kiện ~c~, bí ngô được gọi là "đặc biệt" nếu nó được trang trí phụ kiện ~c~ xòn cha của nó thì không, có hai trường hợp:

• Nếu ~x~ hoặc một trong các cha của nó đặc biệt thì đáp án là ~sub_x~.
• Ngược lại, đáp án là số bí ngô trong cây có gốc là các bí ngô đặc biệt thuộc cây bí ngô ~x~.

Như vậy, kết quả ứng với ~x~ của mỗi truy vấn loại ~2~ là:

~sub_x \times~ các bí ngô đặt biệt là cha của ~x~ ~+ ∑ sub_y~ (~y~ là các bí ngô đặc biệt thuộc cây bí ngô gốc ~x~).

Phần 1: các bí ngô đặc biệt là cha của ~x~.

Khi thêm một bí ngô đặc biệt ~k~, sử dụng cây BIT cập nhật các bí ngô trên đoạn ~[st_k, en_k]~ thêm ~1~ đơn vị. Kết quả sẽ là số bí ngô tại điểm ~st_x~.

Phần 2: ~∑ sub_y~ (~y~ là các bí ngô đặc biệt thuộc cây bí ngô gốc ~x~).

Khi thêm một bí ngô đặc biệt ~k~, sử dụng cây BIT cập nhật ~sub_k~ tại vị trí ~st_k~. Kết quả sẽ là tổng số bí ngô trên đoạn ~[st_x + 1, en_x]~ của BIT.

Như vậy, ta sẽ dùng ~2~ cây BIT để tính cho 2 phần. Ngoài ra việc lưu trữ và cập nhật các bí ngô đặc biệt có thể sử dụng CTDL ~map~.

Code tham khảo

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

typedef long long ll;
typedef vector<int> vi; 

#define FOR(i,a,b) for (int i = (a); i < (b); ++i)
#define F0R(i,a) FOR(i,0,a)
#define ROF(i,a,b) for (int i = (b)-1; i >= (a); --i)
#define R0F(i,a) ROF(i,0,a)
#define trav(a,x) for (auto& a: x)

#define pb push_back
#define ub upper_bound
#define s second

const int MX = 200005;

template<class T, int SZ> struct BIT {
    T bit[SZ+1];
    void upd(int pos, T x) {
        for (; pos <= SZ; pos += (pos&-pos)) 
        bit[pos] += x;
    }
    T sum(int r) {
        T res = 0; for (; r; r -= (r&-r)) 
            res += bit[r];
        return res;
    }
    T query(int l, int r) { 
        return sum(r)-sum(l-1); 
    }   
};

BIT<ll,MX> A,B;
map<int,int> col[MX];
int st[MX], en[MX],sub[MX];
int N,Q;
vi adj[MX];
int co;

void dfs(int x, int y) {
    st[x] = ++co;
    trav(t,adj[x]) if (t != y) dfs(t,x);
    en[x] = co;
    sub[x] = en[x]-st[x]+1;
}

void upd(int x, int y) {
    A.upd(st[x],y); A.upd(en[x]+1,-y);
    B.upd(st[x],y*sub[x]);
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> N >> Q;
    F0R(i,N-1) {
        int a,b; cin >> a >> b;
        adj[a].pb(b), adj[b].pb(a);
    }
    dfs(1,0);
    F0R(i,Q) {
        int t; cin >> t;
        if (t == 1) {
            int x,c; cin >> x >> c;
            auto it = col[c].ub(st[x]);
            if (it != begin(col[c]) && en[prev(it)->s] >= en[x]) continue;
            while (it != end(col[c]) && en[it->s] <= en[x]) {
                upd(it->s,-1);
                col[c].erase(it++);
            }
            col[c][st[x]] = x; upd(x,1);
        } else {
            int x; cin >> x;
            cout << sub[x]*A.sum(st[x])+B.query(st[x]+1,en[x]) << "\n";
        }
    }
}