BOJ 23050 데칼코마니 트리

문제 링크입니다.

문제 요약

주어진 트리를 평면에 선대칭으로 임베딩하세요.

풀이

센트로이드가 유일하다고 가정합시다. 만약 그렇지 않다면 센트로이드는 서로 인접한 정점 두 개고, 이때는 두 센트로이드 사이에 더미 정점 하나를 끼워넣으면 됩니다.

유일한 센트로이드는 반드시 대칭축 위에 있습니다. 또한 대칭축 위의 정점들은 하나의 path를 이루어야 합니다. 각 정점마다 자식 서브트리를 대칭으로 배열했을 때 몇 개의 서브트리가 남는지 확인합니다. 센트로이드를 루트로 잡으면, 센트로이드가 아니고 2 이상인 경우 또는 센트로이드고 3 이상인 경우에는 해당 정점이 대칭축 위에 놓일 수 없음을 알 수 있습니다. 매칭되지 않은 자식 서브트리가 존재하는 경우 해당 자식 서브트리를 대칭축 위에 놓을 수 있는지 또한 확인해야 합니다.

배치가 가능하다면 다시 센트로이드부터 내려가면서 대칭이 되는 정점끼리 매칭하면 됩니다. 서브트리의 매칭은 트리 동형 사상을 통해 구현하면 되고, 해시값 순서대로 자식들을 정렬해 두면 이를 재활용해 정점끼리 매칭하는 과정 역시 빠르게 구현할 수 있습니다.

총 시간 복잡도 $O(N \lg N)$에 문제를 해결할 수 있습니다.

코드

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
const ll mod1 = 99124787, mod2 = 23905856;

vector<int> e[1010101], s[1010101];
int ans[1010101], sz[1010101], n;
pll h[1010101]; bool sym[1010101];
pll H(pll p){
	return {(p.first*p.first%mod1*p.first%mod1+5*p.first*p.second%mod1+23497)%mod1, (p.second*p.second%mod2*6%mod2+p.second*13%mod2+p.first)%mod2};
}

int getSize(int now, int pre){
	sz[now] = 1;
	for(auto nxt : e[now]){
		if(nxt == pre) continue;
		sz[now] += getSize(nxt, now);
	}
	return sz[now];
}

int getCent(int now, int pre){
	for(auto nxt : e[now]){
		if(nxt == pre) continue;
		if(sz[nxt]*2 > n) return getCent(nxt, now);
	}
	return now;
}

bool getHash(int now, int pre, int allow){
	vector<int>& sub = s[now]; sym[now] = 1;
	pll& ret = h[now]; ret = {1,1};
	for(auto& nxt : e[now]) if(nxt != pre){
		getHash(nxt, now, 1);
		sub.push_back(nxt);
		ret = {(ret.first+h[nxt].first)%mod1, (ret.second+h[nxt].second)%mod2};
	} ret = H(ret);
	sort(sub.begin(), sub.end(), [&](int& a, int& b){
		return h[a] < h[b];
	});
	bool last = 0;
	for(int i = 0; i < sub.size(); i++){
		if(last){last = 0; continue;}
		if(i != sub.size()-1 && h[sub[i]] == h[sub[i+1]]){last = 1; continue;}
		allow--; if(sym[sub[i]] != 1) sym[now] = 0;
	} if(allow < 0) sym[now] = 0; return sym[now];
}

void match(int r1, int r2){
	ans[r1] = r2; ans[r2] = r1;
	for(int i = 0; i < s[r1].size(); i++) match(s[r1][i], s[r2][i]);
}

void f(int now){
	bool last = 0;
	for(int i = 0; i < s[now].size(); i++){
		if(last){last = 0; continue;}
		if(i != s[now].size()-1 && h[s[now][i]] == h[s[now][i+1]]){last = 1; match(s[now][i], s[now][i+1]); continue;}
		f(s[now][i]);
	}	
}

bool solve(int now){
	getSize(now, 0);
	int root = getCent(now, 0);
	getSize(root, 0);
	for(auto nxt : e[root]) if(sz[nxt]*2 == n || (sz[root]*2 == n && sz[root] < sz[nxt])){
		for(int i = 0; i < e[root].size(); i++) if(e[root][i] == nxt) e[root].erase(e[root].begin()+i--);
		for(int i = 0; i < e[nxt].size(); i++) if(e[nxt][i] == root) e[nxt].erase(e[nxt].begin()+i--);
		e[root].push_back(n+1); e[nxt].push_back(n+1); e[n+1].push_back(root); e[n+1].push_back(nxt); root = n+1;
	}
	bool ret = getHash(root, 0, 2); if(ret) f(root);
	return ret;
}

int main(){
	cin.tie(0);cout.tie(0);ios::sync_with_stdio(false);
	cin >> n; for(int i = 1; i <= n; i++) ans[i] = i; for(int i = 1; i < n; i++){
		int u, v; cin >> u >> v; e[u].push_back(v); e[v].push_back(u);
	}
	if(!solve(1)) return cout << "NO", 0;
	cout << "YES\n"; 
	for(int i = 1; i <= n; i++) cout << ans[i] << ' ';
}