백준 17399 트리의 외심
https://www.acmicpc.net/problem/17399
숭고한 공식 풀이는 여기서 보실 수 있습니다.
제가 낸 문제입니다!! 처음으로 boj에 올린 문제인데, 꽤 잘 만든 것 같습니다. ㅎㅎ
결론부터 말하자면 세 노드 (A,B),(A,C),(B,C)의 중심 중에 하나가 트리의 외심이 될 수 있습니다. 이 정점 외에는 트리의 외심을 만족하는 정점은 존재하지 않습니다.
간단하게 증명을 해보겠습니다. 우리는 A,B,C를 모두 포함하는 가장 작은 subtree G를 생각할 수 있습니다.
보조정리 1. G 외부에서 3개의 노드로부터 같은 거리에 있는 노드 X가 존재한다면 G 내부에 3개의 노드와 더 가까운 노드 Y가 존재한다.
트리이기 때문에 X에서 A,B,C로 가는 경로가 유일합니다. 따라서 X에서 G로 가는 최단경로 또한 유일하고 이 만큼 X를 G로 이동시키면 더 가까운 노드 Y가 존재합니다.
즉, 외심이 존재한다면 이는 G 위에 있다는 사실이 증명되었습니다.
보조정리 2. G 위에서 A,B,C의 외심은 유일하거나 존재하지 않는다.
2개 이상의 외심 O1, O2가 존재한다고 가정해 봅시다.
G위에 있으므로 $ O_1O_2=0 $ 이고 모순입니다.
따라서 G위에 외심은 유일하거나 존재하지 않습니다.
보조정리 3. 외심이 존재한다면, 외심의 후보는 (A,B), (B,C), (A,C)의 중심 3개뿐입니다.
외심이 후보가 아닌 노드에 있다고 가정합시다.
또, $ M(A,B)=M_1, M(A,C)=M_2, M(B,C)=M_3 $ 라 합시다.
가정에 의하여 $ OM_1>0 $ 이므로 $A,B,L_1$ 을 포함하는 subtree 외부에 있습니다.
같은 방식으로 하여 O는 $ A,C,L_2 $ subtree 외부, $ B,C,L_2 $ subtree 외부에 있습니다.
O는 G위에 있는데 G와 3개의 subtree의 교집합이 공집합이므로 모순입니다.
따라서 외심의 후보는 3개 뿐입니다.
즉, 3개의 후보에 대하여 A,B,C까지의 거리가 모두 같은지 확인하고, 모두 같다면 트리의 외심이 되고 모두 같지 않다면 트리의 외심이 아니게 됩니다.
트리에서 두 노드의 중심은 LCA 알고리즘을 이용하면 쿼리당 log(n)의 시간복잡도로 구할 수 있습니다.
#include<bits/stdc++.h>
using namespace std;
const int SZ=100005;
const int MXH=18;
vector<int> graph[SZ];
int par[MXH][SZ];
int lv[SZ];
int vst[SZ];
int n;
void dfs(int x, int parent, int level){
vst[x]=1;
par[0][x]=parent;
lv[x]=level;
for(int nxt:graph[x]){
if(vst[nxt]==1) continue;
dfs(nxt,x,level+1);
}
}
void memo(){
for(int i=1;i<MXH;i++){
for(int j=1;j<=n;j++){
par[i][j]=par[i-1][par[i-1][j]];
}
}
}
int level_up(int x, int diff){
for(int i=MXH-1;i>=0;i--){
if((1<<i)&diff) x=par[i][x];
}
return x;
}
int lca(int x, int y){
x=level_up(x,max(0,lv[x]-lv[y]));
y=level_up(y,max(0,lv[y]-lv[x]));
if(x==y) return x;
for(int i=MXH-1;i>=0;i--){
if(par[i][x]!=par[i][y]){
x=par[i][x];
y=par[i][y];
}
}
return par[0][x];
}
int tree_dist(int a, int b){
int l=lca(a,b);
return lv[a]+lv[b]-2*lv[l];
}
int iso(int a, int b){
int up=tree_dist(a,b);
if(up%2==1) return -1;
if(lv[a]>lv[b]) return level_up(a,up/2);
else return level_up(b,up/2);
}
int query(int a, int b, int c){
int m1=iso(a,b);
int m2=iso(a,c);
int m3=iso(b,c);
if(m1!=-1){
if(tree_dist(a,m1)==tree_dist(b,m1) && tree_dist(b,m1)==tree_dist(c,m1)) return m1;
}
if(m2!=-1){
if(tree_dist(a,m2)==tree_dist(b,m2) && tree_dist(b,m2)==tree_dist(c,m2)) return m2;
}
if(m3!=-1){
if(tree_dist(a,m3)==tree_dist(b,m3) && tree_dist(b,m3)==tree_dist(c,m3)) return m3;
}
return -1;
}
int main(void){
ios::sync_with_stdio(false); cin.tie(NULL);
cin>>n;
for(int i=1;i<n;i++){
int x,y; cin>>x>>y;
graph[x].push_back(y);
graph[y].push_back(x);
}
dfs(1,0,0);
memo();
int q; cin>>q;
while(q--){
int x,y,z; cin>>x>>y>>z;
cout<<query(x,y,z)<<'\n';
}
return 0;
}
