CF1605D. Treelabeling
题意
给出一棵树，两个人玩游戏，轮流走向旁边的点（须满足u xor v<min(u,v)），走不了就输了。要求给出一组放置数字的方法，使得在所有位置开始游戏时，先手能赢的点数最多。
解法
考虑第一步就走不了（即先手直接赢），只需二进制第一位u与v一个为1一个为0。考虑对树作二分图，假设有k个白点（假设k=（100110）（2）），对每一个二进制中的1（比如倒数第三个），则选取100,101,110,111四个结点作白点，这样总结点个数正好等于k，依次匹配即可。
//https://blog.csdn.net/Sherlock_Holmewei/article/details/121349418
#include <bits/stdc++.h>
#define For(i,a,b) for(int i=a;i<=b;i++)
using namespace std;
const int N=400005;
int t,n,cnt;
int head[N],c[3][N],ans[N];
bool vis[N],used[N];
struct node {
int next,to;
} sxd[N];
void add(int x,int y) {
sxd[++cnt].next=head[x];
sxd[cnt].to=y;
head[x]=cnt;
}
void dfs(int x,int col) {
vis[x]=1;
c[col][++c[col][0]]=x;
for(int i=head[x];i;i=sxd[i].next) {
int to=sxd[i].to;
if(!vis[to]) dfs(to,3-col);
}
}
signed main() {
cin>>t;
while(t--) {
cin>>n;
int x=0,y=0;
cnt=0;
c[1][0]=c[2][0]=0;
For(i,1,n-1) {cin>>x>>y; add(x,y); add(y,x);}
For(i,1,n) if(!vis[i]) dfs(i,1);
int at=0,now=0,which=0;
if(c[1][0]<=c[2][0]) {now=c[1][0],which=1;}
else {now=c[2][0],which=2;}
For(i,0,30) if((now>>i)%2==1) {
if(i==0) {
ans[c[which][++at]]=1;
used[1]=1;
}
if(i!=0) For(j,pow(2,i),min(n,(int)pow(2,i+1)-1)) {
ans[c[which][++at]]=j;
used[j]=1;
}
}
int cd=0;
For(i,1,n) if(!used[i]) ans[c[3-which][++cd]]=i;
For(i,1,n) cout<<ans[i]<<" ";
puts("");
For(i,1,min(n<<2,400000)) head[i]=vis[i]=ans[i]=used[i]=0;
}
return 0;
}