【题解】LuoGu6147：[USACO20FEB]Delegation G_delegation csdn usaco-CSDN博客

本文链接：https://blog.csdn.net/ModestCoder_/article/details/108834811

本文针对赛道修建问题提出了一种优化方案。通过对KKK值的枚举，并利用两个关键优化策略——确保KKK为(n−1)(n-1)(n−1)的因数且不超过直径长度，来加速求解过程。通过遍历树形结构并评估各子树间的配对可能性，最终确定了合理的赛道布局。

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

原题传送门
这道题是 $赛道修建$ 的弱化版
枚举 $K$
这里有两个优化

$K$ 必须是 $(n - 1)$ 的因数
$K$ 必须小于等于直径

对于每个 $K$ ，判断是否合理，那么就跑一遍树
对于某一个点，下面有一堆儿子剩下来的链
对于每条链，设长度为 $x$ ，那么必须有一条长度为 $K - x$ 的链与之配对，否则这条链就必须跟着自己这个点一起往上传
但是如果有多条链无法配对，跟着自己上传的链又最多只能有一条，那么就不合理

Code：

#include <bits/stdc++.h>
#define maxn 1000010
using namespace std;
struct Edge{
	int to, next;
}edge[maxn << 1];
int num, head[maxn], rt, D, n, ifyes, a[maxn], m, cnt[maxn], dp[maxn], base;

inline int read(){
	int s = 0, w = 1;
	char c = getchar();
	for (; !isdigit(c); c = getchar()) if (c == '-') w = -1;
	for (; isdigit(c); c = getchar()) s = (s << 1) + (s << 3) + (c ^ 48);
	return s * w;
}

void addedge(int x, int y){ edge[++num] = (Edge){y, head[x]}, head[x] = num; }

void dfs(int u, int pre, int s){
	if (s > D) D = s, rt = u;
	for (int i = head[u]; i; i = edge[i].next){
		int v = edge[i].to;
		if (v != pre) dfs(v, u, s + 1);
	}
}

void calcd(){
	dfs(1, 0, 0);
	dfs(rt, 0, 0);
}

void Dp(int u, int pre){
	dp[u] = 0;
	for (int i = head[u]; i; i = edge[i].next){
		int v = edge[i].to;
		if (v != pre) Dp(v, u);
		if (!ifyes) return;
	}
	m = 0;
//	puts("modest");
//	for (int i = 1; i <= n; ++i) printf("%d", cnt[i]);
//	puts("coder");
	for (int i = head[u]; i; i = edge[i].next){
		int v = edge[i].to;
		if (v != pre){
			if (dp[v] + 1 < base) ++cnt[a[++m] = dp[v] + 1];
		}
	}
//	sort(a + 1, a + 1 + m);
//	printf("u=%d\n", u);
//	for (int i = 1; i <= m; ++i) printf("%d ", a[i]); puts("");
	int flag = 0;
	for (int i = m; i; --i)
		if (cnt[a[i]]){
			if (a[i] == base - a[i]){
				if (cnt[a[i]] & 1){
					if (flag){ ifyes = 0; cnt[a[i]] = 0; }
					flag = 1, dp[u] = a[i];
				}
			} else
			if (cnt[a[i]] != cnt[base - a[i]]){
				if (flag || abs(cnt[a[i]] - cnt[base - a[i]]) > 1){
					ifyes = 0; cnt[a[i]] = cnt[base - a[i]] = 0;
				}
				flag = 1;
				if (cnt[a[i]] > cnt[base - a[i]]) dp[u] = a[i]; else dp[u] = base - a[i];
			}
			cnt[a[i]] = cnt[base - a[i]] = 0;
		}
//	printf("dp[%d]=%d\n", u, dp[u]);
}

int main(){
	freopen("delegation.in", "r", stdin);
	freopen("delegation.out", "w", stdout);
	n = read();
	for (int i = 1; i < n; ++i){
		int x = read(), y = read();
		addedge(x, y), addedge(y, x);
	}
	calcd();
	printf("1");
	for (int i = 2; i <= D; ++i)
		if ((n - 1) % i == 0){
			base = i, ifyes = 1;
//			printf("base = %d\n", base);
			Dp(1, 0);
			printf("%d", ifyes);
		} else printf("0");
	for (int i = D + 1; i < n; ++i) printf("0");
	return 0;
}