题解 P6147 【[USACO20FEB]Delegation G】

· · 题解

原图是一棵无根树，为了方便起见，我们指定 1 号点为根。

接下来我们从 1 号点开始遍历整棵树。

画个图后会发现，一条经过点 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;
}