CF1605D. Treelabeling(二分图 博弈)

linkkk

给出 n n n个节点的树，每个点都有一个权值，能够从 u u u走到 v v v的条件是 w u ⊕ w v < = m i n ( w u , w v ) w_uoplus w_v<=min(w_u,w_v) wu​⊕wv​<=min(wu​,wv​)
两人轮流在树上操作，起点不固定，问如何构造一种方案使得后手胜的次数最多。

一种极端的情况就是从哪个点出发都不可以走，这样无论先手选择哪个点，后手一定胜利。
也就是说，如何构造方案使得树上任意两点是不可达的？
w u ⊕ w v > m i n ( w u , w v ) w_uoplus w_v>min(w_u,w_v) wu​⊕wv​>min(wu​,wv​)表示两者的最高位不同，可以对整个树进行二分图染色，或者按深度为奇数/偶数分类。
记录最高位为 0 / 1 0/1 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
using namespace std;
typedef long long ll;typedef unsigned long long ull;
typedef pairPLL;typedef pairPII;typedef pairPDD;
#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;

vectorg[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<