[2022.04.20.] GALAKSIJA

문제 정보

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

난이도: Platinum I

분류: [자료구조 → 분리 집합 (DSU) → Small to Large] [오프라인 쿼리]

 

문제 요약

트리 \( T = (V, E) \)가 주어질 때, (초기 상태를 포함해) 간선을 하나씩 자를 때마다 아래 문제의 답을 출력하면 됩니다.

• 임의의 두 정점 \( v \neq w \)에 대해, \( v \)에서 \( w \)로 가는 경로에 속한 간선들의 가중치를 XOR한 값이 0인 정점쌍 \( (v, w) \)의 개수. (\( (v, w)\)와 \( (w, v) \)는 같은 것으로 취급한다.)

 

풀이

간선을 자르기만 합니다. 보통 이럴 때 하는 건 '쿼리를 역순으로 처리하면서 간선을 잇기'가 되죠.

 

이제 어떤 간선 \( v \leftrightarrow w \)를 이을 때가 되었다고 합시다.

그리고 간선을 잇기 직전의 포레스트의 상태를 \( T' \)이라고 하고, 아래 값들을 정의해봅시다.

\( w_{v} := \) \( v \)를 포함하는 트리의 루트를 \( v' \)이라 할 때, \( v' \Rightarrow v \)의 경로 XOR 값

\( W_{v, x} := \) \( v \)를 루트로 하는 트리 \( T'_{v} \)에서, 같은 트리 내에 속한 임의의 정점 \( w \)에 대해 \( v \Rightarrow w \)의 경로에 속한 간선들의 가중치 XOR 값이 \( x \)인 \( w \)의 개수

 

이제 \( a \xrightarrow{c} b \) 간선을 이을 때, 답이 얼마나 변화하는지 생각해봅시다.

\( a \)와 \( b \)를 포함하는 트리의 루트를 각각 \( a', b' \)이라고 합시다.

 

그럼 \( v \in T_{a'} \)과 \( w \in T_{b'} \)에 대해, \( v \Rightarrow w \)의 경로는 아래 방식으로 나눠볼 수 있습니다.

\( v \Rightarrow a' \Rightarrow a \rightarrow b \Rightarrow b' \Rightarrow w \)

이 과정에서 같은 간선을 2번 지날 수는 있지만, 어차피 2번 지나면 XOR 값이 취소되므로 신경쓰지 않아도 됩니다.

 

이제 여기서 \( a \rightarrow b \)의 간선을 \( a' \Rightarrow a \rightarrow b \Rightarrow b' \)으로 바꿔봅시다.

이러면, 새로운 간선 값은 \( w_{a} \oplus c \oplus w_{b} \)가 됩니다.

이제 여기서 \( v \Rightarrow w \)의 개념을 없애고 개수만 세보면, \( x \oplus (w_{a} \oplus c \oplus w_{b}) \oplus y = 0 \)인 모든 \( (x, y) \) 쌍에 대해 \( DP_{a', x} \times DP_{b', y} \)개의 XOR = 0인 경로가 새로 나오게 됩니다.

 

+ 원래 있던 간선이 없어지지는 않으니, 원래 있던 경로가 없어지는 경우는 존재하지 않습니다.

 

포레스트에서 시작해서 트리가 합쳐지니, 위 과정을 Union-Find와 병행해서 하면 됩니다.

물론, Union-Find만으로는 \( O(N^2) \)이 나오게 되니 Small to Large Technique를 사용해 \( O(N \log N) \)으로 시간을 줄여주면 됩니다.

pi3 edg[100020]; int qry[100020];
int par[100020], val[100020]; vector<int> vtx[100020]; map<int, int> num[100020];

int fnd(int a){
	if (par[a] == a){ return a; }
	return par[a] = fnd(par[a]);
}

ll res = 0; stack<ll> ans;
void upd(int a, int b, int c){
	c ^= val[a] ^ val[b];
	int pa = fnd(a), pb = fnd(b);
	if (vtx[pa].size() > vtx[pb].size()){ swap(a, b); swap(pa, pb); }
	for (pi2 p : num[pa]){ res += (ll)num[pb][p.fr^c] * p.sc; }
	for (int x : vtx[pa]){
		val[x] ^= c; vtx[pb].push_back(x);
		num[pb][ val[x] ] += 1;
	}
	par[pa] = pb;
	vtx[pa].clear(); num[pa].clear();
}

void Main(){
	int n; cin >> n;
	for (int i = 1; i <= n; i++){ par[i] = i; vtx[i].push_back(i); num[i][0] = 1; }
	for (int i = 1; i < n; i++){ cin >> edg[i].fr.fr >> edg[i].fr.sc >> edg[i].sc; }
	ans.push(0);
	for (int i = 1; i < n; i++){ cin >> qry[i]; }
	for (int i = n-1; i >= 1; i--){
		int idx = qry[i];
		upd(edg[idx].fr.fr, edg[idx].fr.sc, edg[idx].sc);
		ans.push(res);
	}
	while (!ans.empty()){ cout << ans.top() << endl; ans.pop(); }
}