OI XXVIII - gan (Alt)

// https://szkopul.edu.pl/problemset/problem/v7LhQdIK3z6mWSVH4I7F266w/site/?key=statement

// Gang Biciaków
// XXVIII OI

#include <bits/stdc++.h>

const int MAXN = 100005;
const int MAXM = 150005;
const int MAXZ = 150005;
const int MAX_ET = 200005;

struct Query {
    char type;
    int a, b;
    int id;
};

std::vector<std::pair<int, int>> adj[MAXN];
int initial_edge_color[MAXN];
int current_edge_color[MAXN];

int et_edge[MAX_ET];
int et_dir[MAX_ET];
int pos[MAXN];
int edge_in[MAXN];
int edge_out[MAXN];
int et_len = 0;

int cnt[MAXM];
int distinct_count = 0;
int ans[MAXZ];

void dfs(int u, int p) {
    for (auto& edge : adj[u]) {
        int v = edge.first;
        int id = edge.second;
        if (v == p) continue;

        edge_in[id] = et_len;
        et_edge[et_len] = id;
        et_dir[et_len] = 1;
        pos[v] = et_len;
        et_len++;

        dfs(v, u);

        edge_out[id] = et_len;
        et_edge[et_len] = id;
        et_dir[et_len] = -1;
        et_len++;
    }
}

inline void add_val(int c) {
    if (cnt[c] == 0) distinct_count++;
    cnt[c]++;
}

inline void remove_val(int c) {
    cnt[c]--;
    if (cnt[c] == 0) distinct_count--;
}

int main() {
    std::ios_base::sync_with_stdio(0);
    std::cin.tie(0);
    std::cout.tie(0);

    int n, m, z;
    std::cin >> n >> m >> z;

    for (int i = 1; i < n; i++) {
        int u, v, c;
        std::cin >> u >> v >> c;
        adj[u].push_back({v, i});
        adj[v].push_back({u, i});
        initial_edge_color[i] = c;
    }

    pos[1] = -1;

    dfs(1, 0);

    std::vector<Query> queries(z);
    for (int i = 0; i < z; i++) {
        char t;
        std::cin >> t;
        queries[i].type = t;
        if (t == 'Z') {
            std::cin >> queries[i].a;
            queries[i].id = i;
        } else {
            std::cin >> queries[i].a >> queries[i].b;
            queries[i].id = i;
        }
    }

    int block_size = sqrt(et_len);
    if (block_size < 1) block_size = 1;

    for (int L = 0; L < et_len; L += block_size) {
        int R = std::min(L + block_size - 1, et_len - 1);

        distinct_count = 0;
        memset(cnt, 0, sizeof(int) * (m + 1));
        for (int i = 1; i < n; i++)
            current_edge_color[i] = initial_edge_color[i];

        for (int k = 0; k < L; k++) {
            int e = et_edge[k];
            int d = et_dir[k];
            int c = current_edge_color[e];
            if (d == 1)
                add_val(c);
            else
                remove_val(c);
        }

        for (int i = 0; i < z; i++) {
            if (queries[i].type == 'B') {
                int e = queries[i].a;
                int new_c = queries[i].b;
                int old_c = current_edge_color[e];

                current_edge_color[e] = new_c;

                if (edge_in[e] < L && edge_out[e] >= L) {
                    remove_val(old_c);
                    add_val(new_c);
                }
            } else {
                int u = queries[i].a;
                int p = pos[u];

                if (p >= L && p <= R) {
                    for (int k = L; k <= p; k++) {
                        int e = et_edge[k];
                        int d = et_dir[k];
                        int c = current_edge_color[e];
                        if (d == 1)
                            add_val(c);
                        else
                            remove_val(c);
                    }

                    ans[queries[i].id] = distinct_count;

                    for (int k = p; k >= L; k--) {
                        int e = et_edge[k];
                        int d = et_dir[k];
                        int c = current_edge_color[e];
                        if (d == 1)
                            remove_val(c);
                        else
                            add_val(c);
                    }
                } else if (p == -1 && L == 0) {
                    ans[queries[i].id] = 0;
                }
            }
        }
    }

    for (int i = 0; i < z; i++) {
        if (queries[i].type == 'Z') {
            std::cout << ans[i] << "\n";
        }
    }

    return 0;
}