문제 요약.
트리에서 게임을 진행할건데,
라는 조건을 만족할때만 $u$ 에서 $v$로 움직일 수 있다.
못움직이면 질때, 선공이 이기는 정점이 최대화 하도록, 정점의 번호를 재배열 하여라.
3번 조건을 단순화 하자.
$u \leq v$라고 가정해도 일반성을 잃지 않는다.
u의 켜져 있는 bit 중 가장 큰 bit 를 bit_u, v의 켜져있는 bit 중 가장 큰 bit을 bit_v라고 하면
1.bit_u<bit_v 라면 u^v > u 이다. 따라서 모순
2. bit_u>bit_v라면 u>v이다. 모순
따라서 bit_u = bit_v일수밖에 없고, bit_u =bit_v라면 u^v <u이므로 동치이다.
따라서 3번 조건은 이렇게 바뀐다.
가장 큰 비트가 같을때만 그 정점으로 움직일 수 있다.
그런데 bit연산의 특성상, 가장 큰 비트가 1인거의 개수는 1, 2인거의 개수는 2, 3인거의 개수는 4....꼴이니까
$1 2 4 8 16...... 2^k, a $ (다 더하면 n) 꼴이어야 한다.
그럼 여기서 생각할 수 있는게, 어떻게 잘 배열하면 모든 정점을 골라도 항상 선공이 이기게 할 수 있다는 직관을 가져야 한다. 트리는 이분 그래프이기 때문에 가장 많이 나온 bit 랑 인접한 정점을 나머지 bit로 채울 수 있을까? 라는 생각을 가지면 되는데, 제일 큰 bit 집합 크기 - 나머지 집합 크기 합 $\leq$ 이분 그래프의 두 color개수 차이 라면 성립한다.
그런데, 제일 큰 bit 그룹 수 보다 나머지 집합 크기 합이 최대 1 차이 난다. 그런데 1 차이 날때는 n이 홀수라 그래프의 color 개수 차이도 1차이 난다. 따라서 항상 성립한다.
constructive하는 방법을 생각해보자. 이진수를 만드는것처럼 하면 된다.
#include<bits/stdc++.h>
//#define double long double
//T.erase(unique(T.begin(),T.end()),T.end());
//written by djs100201
#define all(v) v.begin(),v.end()
using namespace std;
using ll = long long;
using P = pair<ll, ll>;
using PP = pair<ll, P>;
const ll n_ = 3e5 + 100, inf = 2e18 + 1, mod = 998244353, sqrtN = 320;
ll dy[4] = { -1,0,1,0 }, dx[4] = { 0,1,0,-1 };
ll n, m, k, tc = 1, a, b, c, d, sum, x, y, z, w, base, ans, q;
ll gcd(ll x, ll y) {
if (!y)return x;
return gcd(y, x % y);
}
vector<ll>v[n_], A[n_];
ll dp[n_], root, dist, checked[n_];
void dfs(ll x, ll par) {
if (dp[x])a++;
else b++;
for (auto nxt : v[x]) {
if (nxt == par)continue;
if (dp[x])dp[nxt] = 0;
else dp[nxt] = 1;
dfs(nxt, x);
}
}
void solve() {
cin >> n;
if (n == 1) {
cout << 1 << '\n';
return;
}
for (int i = 1; i < n; i++) {
cin >> a >> b;
v[a].push_back(b);
v[b].push_back(a);
}
a = 1, b = 0;
for (int i = 1; i <= n; i++) {
if (i >= a * 2)a *= 2, b++;
A[b].push_back(i);
}
x = 0;
vector<P>S;
for (int i = 0; i < 100; i++) {
if (A[i].size() == 0)continue;
S.push_back({ A[i].size(),i });
}
sort(all(S));
a = 0, b = 0;
dfs(1, 0);
if (a < b) {
swap(a, b);
z = 1;
}
else z = 0;
base = 0;
c = b;
while (b) {
if (b % 2)checked[base] = true;
b /= 2, base++;
}
b = c;
vector<ll>sm, la;
for (int i = 0; i <=100; i++) {
if (A[i].size() == 0)continue;
for (auto nxt : A[i]) {
if (checked[i])sm.push_back(nxt);
else la.push_back(nxt);
}
}
assert(sm.size() == b);
for (int i = 1; i <= n; i++) {
if (dp[i] == z) {
cout << sm.back() << ' ';
sm.pop_back();
}
else {
cout << la.back() << ' ';
la.pop_back();
}
}
//a가 항상 b보다 큼
for (int i = 0; i <= n; i++)v[i].clear(), A[i].clear(), checked[i] = 0;
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
cin >> tc;
while (tc--)solve();
}
본라운드 때 봤다면 풀고 떡상했을거 같다.