题意：
给出n个节点的树，每个点都有一个权值，能够从u走到v的条件是w u ⊕ w v < = m i n ( w u , w v )
两人轮流在树上操作，起点不固定，问如何构造一种方案使得后手胜的次数最多。
思路：
一种极端的情况就是从哪个点出发都不可以走，这样无论先手选择哪个点，后手一定胜利。
也就是说，如何构造方案使得树上任意两点是不可达的？
w u ⊕ w v > m i n ( w u , w v )表示两者的最高位不同，可以对整个树进行二分图染色，或者按深度为奇数/偶数分类。
记录最高位为0 / 1的数，跟二分图的两种颜色对应，这样的方案就是任意两点都不可达的了。
参考
代码：
// Problem: D. Treelabeling // Contest: Codeforces Round #754 (Div. 2) // URL: https://codeforces.com/contest/1605/problem/D // Memory Limit: 256 MB // Time Limit: 2000 ms // // Powered by CP Editor (https://cpeditor.org) #include<bits/stdc++.h> using namespace std; typedef long long ll;typedef unsigned long long ull; typedef pair<ll,ll>PLL;typedef pair<int,int>PII;typedef pair<double,double>PDD; #define I_int ll inline ll read(){ll x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}return x*f;} #define read read() #define rep(i, a, b) for(int i=(a);i<=(b);++i) #define dep(i, a, b) for(int i=(a);i>=(b);--i) ll ksm(ll a,ll b,ll p){ll res=1;while(b){if(b&1)res=res*a%p;a=a*a%p;b>>=1;}return res;} const int maxn=2e5+100; vector<int>g[maxn]; int n,col[maxn],sum0,sum1,ans[maxn],num[maxn]; void dfs(int u,int fa,int c){ col[u]=c; if(c==1) sum1++; else sum0++; for(auto t:g[u]){ if(t==fa) continue; dfs(t,u,c^1); } } int main(){ int _=read; while(_--){ n=read; rep(i,1,n-1){ int u=read,v=read; g[u].push_back(v); g[v].push_back(u); } sum0=sum1=0; dfs(1,0,0); if(sum0>sum1){ swap(sum0,sum1); rep(i,1,n) col[i]^=1;///始终保持sum0小 } rep(i,1,n){ int now=30; for(now=30;now>=0;now--) if(i&(1<<now)) break; if(sum0&(1<<now)) num[i]=0; else num[i]=1; } int cnt1=1,cnt0=1; rep(i,1,n){ if(col[i]==0){ while(num[cnt0]==1) cnt0++; ans[i]=cnt0++; } else{ while(num[cnt1]==0) cnt1++; ans[i]=cnt1++; } } rep(i,1,n) cout<<ans[i]<<" "; puts(""); rep(i,1,n) g[i].clear(),col[i]=ans[i]=num[i]=0; } return 0; }
