OI XXVIII - gan (Mo)

// 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 {
    int pos;
    int time;
    int id;
};

struct Update {
    int edge_id;
    int old_color;
    int new_color;
};

int BLOCK_SIZE;
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_in_et[MAXN];
int et_len = 0;

int cnt[MAXM];
int distinct_count = 0;
bool is_active[MAXN];
int ans[MAXZ];

std::vector<Query> queries;
std::vector<Update> updates;

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

        et_edge[et_len] = id;
        et_dir[et_len] = 1;
        pos_in_et[v] = et_len;
        et_len++;

        dfs(v, u);

        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--;
}

bool compareQueries(const Query& a, const Query& b) {
    int block_a = a.pos / BLOCK_SIZE;
    int block_b = b.pos / BLOCK_SIZE;
    if (block_a != block_b) return block_a < block_b;
    return a.time < b.time;
}

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;
        current_edge_color[i] = c;
    }

    pos_in_et[1] = -1;
    dfs(1, 0);

    int time_counter = 0;
    int query_count = 0;

    std::vector<int> temp_colors(n + 1);
    for (int i = 1; i < n; i++)
        temp_colors[i] = initial_edge_color[i];

    for (int i = 0; i < z; i++) {
        char type;
        std::cin >> type;
        if (type == 'Z') {
            int x;
            std::cin >> x;
            queries.push_back({pos_in_et[x], time_counter, query_count++});
        } else {
            int edge, new_c;
            std::cin >> edge >> new_c;
            updates.push_back({edge, temp_colors[edge], new_c});
            temp_colors[edge] = new_c;
            time_counter++;
        }
    }

    BLOCK_SIZE = std::max(1, (int)sqrt(et_len));
    if (et_len > 0) BLOCK_SIZE = (int)(et_len / sqrt(queries.size() + 1)) + 1;
    if (BLOCK_SIZE < 1) BLOCK_SIZE = 1;

    std::sort(queries.begin(), queries.end(), compareQueries);

    int curr_pos = -1;
    int curr_time = 0;

    for (const auto& q : queries) {
        while (curr_time < q.time) {
            int edge = updates[curr_time].edge_id;
            int new_c = updates[curr_time].new_color;
            int old_c = updates[curr_time].old_color;

            current_edge_color[edge] = new_c;

            if (is_active[edge]) {
                remove_val(old_c);
                add_val(new_c);
            }
            curr_time++;
        }

        while (curr_time > q.time) {
            curr_time--;
            int edge = updates[curr_time].edge_id;
            int old_c = updates[curr_time].old_color;
            int cur_c = updates[curr_time].new_color;

            current_edge_color[edge] = old_c;

            if (is_active[edge]) {
                remove_val(cur_c);
                add_val(old_c);
            }
        }

        while (curr_pos < q.pos) {
            curr_pos++;
            int edge = et_edge[curr_pos];
            int dir = et_dir[curr_pos];
            int color = current_edge_color[edge];

            if (dir == 1) {
                is_active[edge] = true;
                add_val(color);
            } else {
                is_active[edge] = false;
                remove_val(color);
            }
        }

        while (curr_pos > q.pos) {
            int edge = et_edge[curr_pos];
            int dir = et_dir[curr_pos];
            int color = current_edge_color[edge];

            if (dir == 1) {
                is_active[edge] = false;
                remove_val(color);
            } else {
                is_active[edge] = true;
                add_val(color);
            }
            curr_pos--;
        }

        ans[q.id] = distinct_count;
    }

    for (int i = 0; i < query_count; i++) {
        std::cout << ans[i] << "\n";
    }

    return 0;
}