rt

思路是先 dfs 一遍求出每个点的深度，然后再一个 dfs 暴力选择。

原来这样应该是 10 分的，但是加了个剪枝：当前选择的节点深度之和大于所有节点深度之和的一半时，就 return。然后。。就 100 了。。

代码如下，个人感觉时间复杂度是 $\mathcal O(2^n)$，不知为何能通过本题。

#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;

int n; long long sum;
vector <int> g[1000005];
int dis[1000005];
bool qwq[1000005];

void dfs(int x , int fa){
	dis[x] = dis[fa] + 1;
	for(int next : g[x]){
		if(next == fa)
			continue;
		dfs(next , x);
	}
}

void dfs2(int x , long long a1 , long long a2){
	if(a1 > sum || a2 > sum)
		return ;
	if(x > n){
		if(a1 != a2)
			return ;
		for(int i = 1;i <= n;i++)
			printf("%d " , qwq[i]);
		exit(0);
	}
	qwq[x] = 0;
	dfs2(x + 1 , a1 + dis[x] , a2);
	qwq[x] = 1;
	dfs2(x + 1 , a1 , a2 + dis[x]);
	qwq[x] = 0;
}

int main(void){
	scanf("%d" , &n);
	for(int i = 1;i < n;i++){
		int u , v;
		scanf("%d%d" , &u , &v);
		g[u].push_back(v);
		g[v].push_back(u);
	}
	dfs(1 , 0);
	for(int i = 1;i <= n;i++)
		sum += dis[i];
	if(sum & 1){
		puts("-1");
		return 0;
	}
	sum >>= 1;
	dfs2(1 , 0 , 0);
	puts("-1");
}

提交记录