自动搬运

查看原文

来自洛谷，原作者为

	StudyingFather 在纷繁杂乱的世界里，独自寻找属于自己的光荣与梦想。

搬运于2025-08-24 22:17:54，当前版本为作者最后更新于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 上提交时 开启 -O2 选项测试点 $3$ 用时 1.27s）。

这种情况下可以考虑对星形图特判处理。

下面是作者在比赛时提交的代码：

（UPD 2021/08/10：感谢 @zhaohaikun 指出了我题解中的一处 实现细节问题，代码已经修正）

#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;
}