BOJ 11813 - GALAKSIJA (disjoint set, tree, 오프라인쿼리)

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

 

http://blog.naver.com/nywoo19/221436385751

위 블로그 참고했습니다.

 

<문제설명>

가중치있는 트리가 주어진다. 간선을 주어진 순서대로 자를 것. 자르고 난 후 원하는 값을 그때 그때 출력하는 문제.

 

원하는 값: 전체 경로에서 경로에포함된 모든 간선의 가중치의 xor값이 0인 경우의 수

 

<풀이>

트리를 자른다 -> 거꾸로 간선을 이어붙이는 편이 훨씬 쉽다.

 

1. a ^ b == 0  <-> a == b

2. xor(u,v) : xor(1,u) ^ xor(1,v)임을 이용해야 한다.

 

map<int,int> mp[MAX]에서

mp[u] = {x, cnt} : 대표값이 u인 set에 포함된 v 중 xor(1,v)값이 x인 것의 개수 cnt

 

간선 (u,v)를 이을 때 생겨나는 새로운 path의 수를 이전 결과에 더해주는 식으로 하면 된다.

 

find(u)에 find(v)셋을 매다는 경우 다음과 같다.

ll merge(int u, int v) {
	u = find(u), v = find(v);
	uf[v] = u;
    
	ll ret = answer.back();
	for (P p : mp[v]) {
		int x, cnt; tie(x, cnt) = p;
		ret += mp[v][x] * mp[u][x];
		mp[u][x] += mp[v][x];
	}
	return ret;
}

 

위와 같이 구현하면 당연히 시간초과가 난다.

작은 셋을 큰 셋에 붙이는 방법을 사용하면 된다.

 

<코드>

ll n, uf[MAX],sz[MAX],order[MAX];
vector<P> adj[MAX], edge;
vector<ll> answer;
map<ll, ll> mp[MAX]; //mp[u] : {1~v까지 xor한 값, 그 개수} //v는u집합요소

int find(int u) {
	if (uf[u] == -1) return u;
	return uf[u] = find(uf[u]);
}
ll merge(int u, int v) {
	u = find(u), v = find(v);
	if (sz[u] < sz[v]) swap(u, v);
	uf[v] = u;
	sz[u] += sz[v];
	sz[v] = 1;
	ll ret = answer.back();
	for (P p : mp[v]) {
		int x, cnt; tie(x, cnt) = p;
		ret += mp[v][x] * mp[u][x];
		mp[u][x] += mp[v][x];
	}
	return ret;
}
void dfs(int u, int p, int xr) {
	mp[u][xr]=1;
	for (P next : adj[u]) if (next.first != p)
		dfs(next.first, u, xr ^ next.second);
}
void init() {
	memset(uf, -1, sizeof(uf));
	fill(sz, sz + n + 1, 1);
	answer.push_back(0);
}

int main() {
	FAST; cin >> n;
	init();
	for (int i = 0, u, v, w; i < n - 1; i++) {
		cin >> u >> v >> w;
		adj[u].push_back({ v,w });
		adj[v].push_back({ u,w });
		edge.push_back({ u,v });
	}
	for (int i = 0; i < n - 1; i++) cin >> order[i];
	dfs(1, 0, 0);
	for (int i = n - 2,u,v; i >= 0; i--) {
		tie(u, v) = edge[order[i] - 1];
		answer.push_back(merge(u, v));
	}
	for (int i = n - 1; i >= 0; i--)
		cout << answer[i] << '\n';
}

 

<생각>

트리를 이어붙일 땐 merge실패를 고려하지 않아도 된다.

 

n개의 요소를 모두 merge할때 작은부분을 큰 부분에 붙이는 상황에서 그때그때 작은 부분에 대해 O(작은부분)만큼 시간을 쓴다면 전체 O(nlogn)이 걸린다(?)

 

트리의 일부에 대한 정보(mp[u])에 완전한 트리(xor(1,v))의 정보를 담아 푸는 경우.