OI XXVIII - gan

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

// Gang Biciaków
// XXVIII OI

#include <bits/stdc++.h>

// #define GARY_DBG
#define GARY_LIB

constexpr int sizikN = 100 * 1001;
constexpr int sizikM = 150 * 1001;
constexpr int rozmiarKubelka = 350;

#define ar std::array

typedef std::vector<std::vector<int>> _kra;

struct Edge {
    int a, b, c;
    Edge(int a1 = 0, int b1 = 0, int c1 = 0) : a(a1), b(b1), c(c1) {}
};
struct Query {
    char t;
    int ix, c, nr;
    Query(char t1 = 0, int ix1 = 0, int c1 = 0, int nr1 = 0) : t(t1), ix(ix1), c(c1), nr(nr1) {}
};

std::vector<std::pair<bool, int>> et;
std::vector<std::pair<int, int>> kra[sizikN];
ar<int, sizikN> in, out, ziomek;
int cnt = 0;
ar<int, sizikM> pref;
int byczkow;

void DFS(int v, int p, int k = -1) {
    if (k != -1) {
        in[k] = cnt++;
        et.push_back({0, k});
        ziomek[v] = in[k];
    }
    for (const auto& [u, x] : kra[v]) {
        if (u != p) {
            DFS(u, v, x);
        }
    }
    if (k != -1) {
        out[k] = cnt++;
        et.push_back({1, k});
    }
}

void solve() {
    int n, m, z;
    std::cin >> n >> m >> z;

    std::vector<Edge> edges(n + 1);
    for (int i = 1; i < n; i++) {
        std::cin >> edges[i].a >> edges[i].b >> edges[i].c;
        kra[edges[i].a].push_back({edges[i].b, i});
        kra[edges[i].b].push_back({edges[i].a, i});
    }

    std::vector<Query> queries(z);
    int q_cnt = 1;
    for (auto& q : queries) {
        q.nr = ++q_cnt;
        std::cin >> q.t;
        if (q.t == 'Z') {
            std::cin >> q.ix;
        } else {
            assert(q.t == 'B');
            std::cin >> q.ix >> q.c;
        }
    }

    et.clear();
    DFS(1, 1);

    std::vector<std::pair<int, int>> ans;

    int L = 0;

    while (L <= (int)et.size()) {
        int R = std::min(L + rozmiarKubelka - 1, (int)et.size() - 1);
        std::vector<int> curr_rodz(n + 1);
        for (int i = 1; i < n; i++) {
            curr_rodz[i] = edges[i].c;
        }
        for (int i = 0; i <= m; i++) {
            pref[i] = 0;
        }
        byczkow = 0;
        for (int k = 0; k < L; k++) {
            if (et[k].first == 1) {
                pref[curr_rodz[et[k].second]]--;
                if (pref[curr_rodz[et[k].second]] == 0) byczkow--;
            } else {
                if (pref[curr_rodz[et[k].second]] == 0) byczkow++;
                pref[curr_rodz[et[k].second]]++;
            }
        }

        for (auto& q : queries) {
            if (q.t == 'Z' && L <= ziomek[q.ix] && ziomek[q.ix] <= R) {
                int starych_byczkow = byczkow;
                for (int i = L; i <= ziomek[q.ix]; i++) {
                    if (et[i].first == 0) {
                        if (pref[curr_rodz[et[i].second]] == 0) byczkow++;
                        pref[curr_rodz[et[i].second]]++;
                    } else {
                        pref[curr_rodz[et[i].second]]--;
                        if (pref[curr_rodz[et[i].second]] == 0) byczkow--;
                    }
                }

                ans.push_back({q.nr, byczkow});

                byczkow = starych_byczkow;
                for (int i = L; i <= ziomek[q.ix]; i++) {
                    if (et[i].first == 0) {
                        pref[curr_rodz[et[i].second]]--;
                    } else {
                        pref[curr_rodz[et[i].second]]++;
                    }
                }
            } else if (q.t == 'B') {
                int old_c = curr_rodz[q.ix];
                curr_rodz[q.ix] = q.c;

                if (in[q.ix] < L && L <= out[q.ix]) {
                    pref[old_c]--;
                    if (pref[old_c] == 0) byczkow--;

                    if (pref[q.c] == 0) byczkow++;
                    pref[q.c]++;
                }
            }
        }

        L += rozmiarKubelka;
    }

    std::sort(ans.begin(), ans.end());
    for (auto& [_, a] : ans) {
        std::cout << a << "\n";
    }
}

int32_t main() {
#ifndef GARY_DBG
    std::ios_base::sync_with_stdio(0);
    std::cin.tie(0);
    std::cout.tie(0);
#endif

    int t = 1;
    // std::cin >> t;

    for (; t > 0; t--) {
        solve();
    }

    return 0;
}