NSOqwq

题解 P6147

题解 P6147 Delegation


分析

首先钦定 $1$ 为根。

注意到经过点 $u$ 的链一定有两种情况:

  • 从点 $u$ 的某个儿子出发,到另一个儿子(1);
  • 从点 $u$ 的某个儿子出发,到 $u$ 的父亲(2)。

注意到第二种情况一定最多只有一条链

那么对于每一个子树,我们要检查,这棵子树是否能被一些长度为 $K$ 的链完全覆盖,或者部分覆盖后,还剩有一条长度 $< K$ 通向根结点的链。

这个过程肯定是需要 dfs 操作的。下面设 $f(u)$ 为遍历点 $u$ 时的返回值。

如果以 $u$ 为根的子树不满足条件,$f(u) =-1$。否则,输出多余的这条链的长度(可能为 $0$)。

对 $u$ 进行 dfs 的时候,首先对于 $u$ 的所有儿子 $v$,一定要进行 $f(v)$,如果任何一个返回 $-1$,那么 $f(u)$ 就返回 $-1$。否则,我们就会有一条长为 $f(v)+1$ 的链。这时,我们把所有这样的链两两配对,成为上面所讲的第一种情况。如果尽可能一一配对后只剩一条短链,那么就返回它的长度;否则返回 $-1$。


实现

对 $u$ 进行 dfs 的时候,对于所有的 $v$,把所有的 $f(v)+1$ 放入一个 multiset $s$ 中维护,如果碰到可以两两配对的情况就从 $s$ 中删去,否则加入 $s$。如果最终 $s$ 的元素个数为 $0$ 或 $1$ 则可以继续,否则就返回 $-1$。

核心部分的实现,评测时建议打开 -O2 优化:

int n;
std::vector<int> e[100001];

int dfs(int u, int fa, int k) {
    std::multiset<int> s;
    for (int v : e[u])
        if (v != fa) {
            int ans = dfs(v, u, k);
            if (ans == -1) return -1;
            ++ans, ans %= k;
            if (ans == 0) continue;
            if (s.count(k - ans))
                s.erase(s.find(k - ans));
            else
                s.insert(ans);
        }
    if (s.size() == 0) return 0;
    if (s.size() == 1) return *s.begin();
    return -1;
}

int main() {
    n = read();
    for (int i = 1; i < n; ++i) {
        int u = read(), v = read();
        e[u].push_back(v),
        e[v].push_back(u);
    }
    for (int i = 1; i < n; ++i)
        if ((n - 1) % i) putchar('0');
        else putchar((dfs(1, 0, i) == 0) + '0');
    putchar('\n');
    return 0;
}

2021-09-02 22:33:19 in 题解