题解：AT_abc397_e [ABC397E] Path Decomposition of a Tree

· · 题解

题目传送门：洛谷 AtCoder

闲话

赛时差点切掉，都怪D题太烦了，我还是太弱了

思路

考虑一般情况，我们要怎么走才能最优呢？随便画一棵树，当且仅当 K = 3，然后就能得到下面的图：

不难发现每次走就像是从下往上找更优，我们再具体看一下，现在给每个节点表上序号：

还是 K = 3 的情况，看到编号为 2 的节点，它有三个子树，分别为 4、5、6，每个子树要么就是分完了，像节点 4、5 一样，恰好有 K 的倍数个儿子节点，所以分完了。否则的话，它就可能有那么一条升上来的链，它的长度一定小于 K ，因为多的你就直接给它分掉就行了。比如你一个子树它有若干条链没有分完，那如果剩下的拼在一起已经不是一个链了，那它就直接无解了。

比如下面的情况，还是 K = 3 的情况：

此时看到编号为 2 的节点，它的三个子树分别再分完后还剩下 5、6、7 三个子节点，但他们已经不是一条链了，所以我们又能发现：一个节点最多允许两个不同的子树剩余，否则形成不了链，无解。

既然剩余不同子树数量大于 2 无解，那如果小于等于 2 又是怎样呢？

思路没问题了，那该怎么实现呢？如果真的按照思路那样从下往上看的话代码会很难写，其实只用从上往下 dfs 一遍，每次返回还剩多少。对当前的某个节点的子节点 dfs，把值存在一个 vector 里，如果像思路里那样数量超过了二就输出 No 然后 exit； 数量等于二就看两个子树剩余子节点数量加上父亲节点 1 是否等于 K，不等于就输出 No 然后 exit，否则就 return 0 表示没有剩余的了； 数量等于一就把那个子树剩余子节点数量加上父亲节点 1 去模 K 看一看还剩多少然后 return 回去； 否则就说明没有剩余的了，直接把这个节点 1 给 return 就行啦。

Code

思路里讲的很清楚了，代码就不具体解释啦。

#include <bits/stdc++.h>
using namespace std;

int n, k;
vector<int> edge[200001];

int dfs(int x, int fa) {
    vector<int> c;
    for (auto i : edge[x]) {
        if (i == fa)
            continue;
        int y = dfs(i, x);
        if (y > 0)
            c.push_back(y);
    }
    if (c.size() >= 3) {
        printf("No");
        exit(0);
    }
    else if (c.size() == 2) {
        if (c[0] + c[1] + 1 != k) {
            printf("No");
            exit(0);
        }
        return 0;
    }
    else if (c.size() == 1)
        return (c[0] + 1) % k;
    return 1;
}

int main() {
    scanf("%d%d", &n, &k);
    for (int i = 1; i < n * k; i++) {
        int u, v;
        scanf("%d%d", &u, &v);
        edge[u].push_back(v);
        edge[v].push_back(u);
    }
    if (k == 1) {
        printf("Yes");
        return 0;
    }
    printf(!dfs(1, 0) ? "Yes" : "No");
}

完美散花！o((>ω< ))o