题解 P6147 【[USACO20FEB]Delegation G】
StudyingFather
2020-03-01 12:47:30
原图是一棵无根树，为了方便起见，我们指定 $1$ 号点为根。
接下来我们从 $1$ 号点开始遍历整棵树。
画个图后会发现，一条经过点 $u$ 的链只可能是如下两种情况之一：
- $v_1 \to u \to v_2$，其中 $v_1,v_2$ 是 $u$ 子树内的某个点（特殊情况下，当然可以和 $u$ 重合）；
- $v \to u \to f$，其中 $v$ 是 $u$ 子树内的某个点，$f$ 是 $u$ 的某个祖先节点。
显然，对于某个点 $u$，第二种链最多只有一条。
于是我们可以对每个点 $u$，维护其等待配对的子链列表。每次遍历到 $u$ 的一个子节点 $v$ 时，将经过 $v$ 的子链尝试与列表中已有的子链配对。如果配对失败就加入等待配对列表。
最后如果存在一个 $u$ 满足其等待配对的子链大于等于两条（根据上面的推导，这种情况下肯定存在一条无法配对的孤链），则无解。
这个做法的效率如何呢？对于一个 $K$，进行检验的时间显然是 $O(N)$ 的，我们需要对 $N-1$ 的每个因子都检验一遍，从而时间复杂度是 $O(N\sigma_0(N-1))$ 的。
数据范围内最坏情况下，$N=83161$ 时 $N-1$ 的因子有 $128$ 个，在星形图（最多只有一个点的度数大于二）的情况下有被卡常数的风险（作者在 USACO 比赛提交时测试点 $3$ 超时（默认开启 `-O2` 优化选项），[在 luogu 上提交时](https://www.luogu.com.cn/record/31235944) 开启 `-O2` 选项测试点 $3$ 用时 1.27s）。
这种情况下可以考虑对星形图特判处理。
下面是作者在比赛时提交的代码：
（UPD 2021/08/10：感谢 @zhaohaikun 指出了我题解中的一处 [实现细节问题](https://www.luogu.com.cn/discuss/show/338901)，代码已经修正）
```cpp
#include <cstdio>
#include <cstring>
#include <iostream>
#include <map>
#include <vector>
using namespace std;
vector<int> e[100005];
int siz[100005], n;
bool dfs(int u, int fa, int k) {
map<int, int> m;
for (auto v : e[u])
if (v != fa) {
if (!dfs(v, u, k)) return false;
int tmp = k - siz[v];
if (m.count(tmp) && m[tmp]) {
m[tmp]--;
if (m[tmp] == 0) m.erase(tmp);
siz[u] -= tmp;
} else if (k != siz[v])
siz[u] += siz[v], m[siz[v]]++;
}
siz[u]++;
int rem = 0;
for (auto p : m) rem += p.second;
return rem <= 1;
}
int main() {
freopen("deleg.in", "r", stdin);
freopen("deleg.out", "w", stdout);
ios::sync_with_stdio(false);
cin >> n;
n--;
for (int i = 1; i <= n; i++) {
int u, v;
cin >> u >> v;
e[u].push_back(v);
e[v].push_back(u);
}
for (int i = 1; i <= n; i++) {
if (n % i)
cout << 0;
else {
memset(siz, 0, sizeof(siz));
if (dfs(1, 0, i))
cout << 1;
else
cout << 0;
}
}
cout << endl;
return 0;
}
```