Delegation (USACO Gold 2020 February)

首先只有 $K$ 是 $N$ 的因子的时候结果才有可能是 $1$ ，否则必须是 $0$ 。

我们指定 $1$ 号节点为树的根，树上的找可行性/方案的问题，经常需要从子树的角度来看。如果整棵树可以划分成两样长度的链之和，则我们看任何一棵子树 $u$ ，会发现与之相关的链只有几种情况：

$v_1 \rightarrow u \rightarrow v_2$ ， $v_1$ 和 $v_2$ 是 $u$ 子树中的节点。
$p \rightarrow u \rightarrow v$ ， $p$ 是 $u$ 的祖先， $v$ 是 $u$ 子树中的节点。极端情况是 $p$ 和 $u$ 重合。
链完全在 $u$ 的某子树内部，就是不经过 $u$

这样的分类，使得我们想到一个类似tree DP的方法： $\text{dfs}(u)$ : 是否有可能将 $u$ 子树内部都分成长度为 $K$ 的链，最后留下一条 $u$ 出发长度 $\leq K$ 的链。

对于一个 $u$ ，我们首先对所有孩子 $v$ 调用 $\text{dfs}(v)$ ，如果有一个返回否，则我们也返回否。如果都是“是”，则剩下的工作，就是要把每个孩子子树中 $v$ 出发的链（长度 $\leq K$ ）互相配对起来，形成尽量多的 $K$ 长的链，这个直接greedy配对就可以了。

复杂度是 $\mathcal{O}(N \cdot N\text{的因子数})$ 。

#include <bits/stdc++.h>
using namespace std;
bool result = true;
int n,k;
vector<int> conn[100005];
int dfs(int pos, int prev) {
    if(result == false) return 0;
    int amn = 0, currtot = 0;
    map<int,int> tot;
 
    for(int i = 0; i < conn[pos].size(); i++) {
        if(conn[pos][i] != prev) {
            int currV = dfs(conn[pos][i],pos) + 1;
            if (result == false) return 0;
            currtot += currV;
            if(currV != k) {
                if(tot.count(k-currV) && tot[k-currV] >= 1) {
                    tot[k-currV]--;
                    amn--;
                }
                else {
                    if (tot.count(currV))
                        tot[currV]++;
                    else
                        tot[currV]=1;
                    amn++;
                }
            }
        }
        if(result == false) return 0;
    }
    if (amn > 1) { result = false; return -1; }
    if (amn == 0) return 0;
    return currtot % k;
}
int main () {
    scanf("%d",&n);
    for(int i = 0; i < n-1; i++) {
        int a,b;
        scanf("%d%d",&a,&b);
        conn[a].push_back(b);
        conn[b].push_back(a);
    }
    printf("1");
    for(int i = 2; i <= n-1; i++) {
        if((n-1)%i == 0) {
            k = i;
            result = true;
            dfs(1,-1);
            printf("%d",result);
        }
        else printf("0");
    }
    printf("\n");
    return 0;
}