Участник:ZhenyaStrelkova/NITTROAD

Материал из DISCOPAL
Перейти к: навигация, поиск

https://www.spoj.com/problems/NITTROAD/

#include <iostream>
#include <stack>
 
using namespace std;
 
const int max_value = 20007;
 
typedef struct Node {
    int u;
    int v;
    int flag;
} node;
 
typedef struct Info {
    int par;
    int count;
    int height;
} info;
 
info dsu[max_value];
node nodes[max_value];
stack<pair<char, int> > qs;
stack<long> answer;
long curr;
 
inline int find(int ver) {
    return (dsu[ver].par == -1) ? ver : find(dsu[ver].par);
}
 
void unite(int u, int v) {
    int ru = find(u);
    int rv = find(v);
 
    curr -= dsu[ru].count * dsu[rv].count;
    if (dsu[rv].height > dsu[ru].height) {
        dsu[ru].par = rv;
        dsu[rv].count += dsu[ru].count;
    } else if (dsu[ru].height > dsu[rv].height) {
        dsu[rv].par = ru;
        dsu[ru].count += dsu[rv].count;
    } else {
        dsu[rv].par = ru;
        dsu[ru].count += dsu[rv].count;
        dsu[ru].height++;
    }
}
 
int main() {
    int T, N, Q, r;
    cin >> T;
    for (int t = 0; t < T; t++) {
        for (int i = 0; i < max_value; i++) {
            dsu[i].par = -1;
            dsu[i].count = 1;
            dsu[i].height = 0;
        }
 
        cin >> N;
        curr = (N * (N - 1)) / 2;
 
        for (int i = 1; i <= N - 1; i++) {
            cin >> nodes[i].u >> nodes[i].v;
            nodes[i].flag = 1;
        }
 
        cin >> Q;
        char ch;
        for (int q = 0; q < Q; q++) {
            cin >> ch;
            if (ch == 'Q') {
                qs.emplace('Q', -1);
            } else {
                cin >> r;
                nodes[r].flag = 0;
                qs.emplace('R', r);
            }
        }
 
        for (int i = 1; i <= N - 1; i++) {
            if (nodes[i].flag == 1) {
                unite(nodes[i].u, nodes[i].v);
            }
        }
 
        while (!qs.empty()) {
            if (qs.top().first == 'Q') {
                answer.push(curr);
            } else {
                r = qs.top().second;
                unite(nodes[r].u, nodes[r].v);
            }
            qs.pop();
        }
 
        while (!answer.empty()) {
            cout << answer.top() << "\n";
            answer.pop();
        }
        cout << "\n";
    }
 
    return 0;
}