📝 문제 정보#
🧐 관찰 및 접근#
- 두 값의 차이를 트리 형태로 저장한다고 생각하자.
- 간선에 가중치가 있는 트리가 될 것이다.
- 두 값 $a, b$가 같은 트리에 있다면 비교 가능하고, 그렇지 않다면 비교 불가능하다.
- 하지만 이 경우 트리가 직선형이 되면, 최악의 경우 $O(N)$이 걸린다.
- 우리는 이러한 경우에 UnionFind에서 경로 압축을 하는 방법을 배웠다.
- 결국 루트까지의 간선 가중치 합을 저장해서 이용하면 된다.
💻 풀이#
- 코드 (C++):
void solve(){
while(1){
int N, M; cin >> N >> M;
if(N + M == 0) break;
UnionFind uf(N);
while(M--){
char op; cin >> op;
if(op == '!'){
int a, b, w; cin >> a >> b >> w;
uf.merge(a-1, b-1, w);
}
else{
int a, b; cin >> a >> b;
auto [ra, wa] = uf.find(a-1);
auto [rb, wb] = uf.find(b-1);
if(ra != rb) cout << "UNKNOWN\n";
else cout << wb - wa << '\n';
}
}
}
}