11813번: GALAKSIJA

https://www.acmicpc.net/problem/11813


$O(n{\lg n}^2)$

w[i]: 1~i 경로상 가중치를 xor 한 것
p~q 경로상 가중치를 xor 한 것과 w[p]^w[q]이 같다.
고로 문제는 w[i]가 같은 쌍의 개수를 구하는 문제가 된다.
이는 map과 유니온 파인드 자료구조를 이용하면 위 시간복잡도에 해결할 수 있다.

간선을 삭제하는 쿼리들을 모두 받아놓은 뒤 반대로 나중 명령부터 처리하여 합집합하는 쿼리로 바꿔보자.
각 집합에 있는 w값 종류 수(집합의 크기)가 작은 쪽에서 큰 쪽으로 원소를 옮기며 합친다.
이 때 집합간 존재하는 w가 같은 쌍의 개수를 누적해준다.
합치는 명령은 총 O(nlgn)번 일어나며 각 원소를 합치는 연산이 O(lgn)이므로 위 시간복잡도가 나온다.

#include<cstdio>
#include<vector>
#include<map>
using namespace std;
const int MXN = 1e5;
int n, e[MXN][3], q[MXN + 1], w[MXN + 1];
vector<pair<int, int> > adj[MXN + 1];
long long r[MXN + 1], s;
struct st {
    int p[MXN + 1];
    map<int, int> mp[MXN + 1];
    void init() { for (int i = 1; i <= n; i++) p[i] = i, mp[i][w[i]]++; }
    int rt(int x) { return x^p[x] ? p[x] = rt(p[x]) : x; }
    void un(int x, int y) {
        int rx = rt(x), ry = rt(y);
        if (mp[rx].size() < mp[ry].size()) swap(rx, ry);
        for (auto it : mp[ry]) {
            s += (long long)mp[rx][it.first] * it.second;
            mp[rx][it.first] += it.second;
        }
        p[ry] = rx;
    }
}uf;
void dfs(int h, int p) {
    for (auto it : adj[h]) if (it.first^p) w[it.first] = w[h] ^ it.second, dfs(it.first, h);
}
int main() {
    scanf("%d", &n);
    for (int i = 1; i<n; i++) {
        scanf("%d%d%d", e[i], e[i] + 1, e[i] + 2);
        adj[e[i][0]].push_back({ e[i][1],e[i][2] });
        adj[e[i][1]].push_back({ e[i][0],e[i][2] });
    }
    for (int i = 1; i < n; i++) scanf("%d", q + i);
    dfs(1, 0);
    uf.init();
    for (int i = n; --i;) uf.un(e[q[i]][0], e[q[i]][1]), r[i] = s;
    for (int i = 1; i <= n; i++) printf("%lld\n", r[i]);
    return 0;
}