[2022.04.20.] GALAKSIJA

문제 정보

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

난이도: Platinum I

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

 

문제 요약

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

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

 

풀이

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

 

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

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

$w_v:=$ $v$를 포함하는 트리의 루트를 $v^{\prime }$이라 할 때, $v^{\prime }\Rightarrow v$의 경로 XOR 값

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

 

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

$a$와 $b$를 포함하는 트리의 루트를 각각 $a^{\prime },b^{\prime }$이라고 합시다.

 

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

$v\Rightarrow a^{\prime }\Rightarrow a\to b\Rightarrow b^{\prime }\Rightarrow w$

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

 

이제 여기서 $a\to b$의 간선을 $a^{\prime }\Rightarrow a\to b\Rightarrow b^{\prime }$으로 바꿔봅시다.

이러면, 새로운 간선 값은 $w_a\oplus c\oplus w_b$가 됩니다.

이제 여기서 $v\Rightarrow w$의 개념을 없애고 개수만 세보면, $x\oplus (w_a\oplus c\oplus w_b)\oplus y=0$인 모든 $(x,y)$ 쌍에 대해 $D{P}_{a^{\prime },x}\times D{P}_{b^{\prime },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(); }
}