ABC397E题解

· · 题解

考虑对于每一个结点，有三种可能：

  1. 和自己的其中一个子节点连为一条链。
  2. 和自己的两个子节点连为一条链，自己为链中间的一个结点。
  3. 自己所有子节点都可以独自构成一条长为 K 的链，自己和父节点连为一条链。

不难发现，所有子节点构成的链的长度中最多只有两条不为 K。当有一条时，可以将当前结点接到这个链上；当有两条时，可以将这两条一左一右和当前结点拼接，即当前结点为这条链中间的一个点，然后计算这个长度，若不为 K 则输出 No。
我们设计一个 dfs 函数，它的返回值为以这个点为端点的链的长度。及只有在第 1 和第 3 种情况时才会返回这个长度，当为第 2 种情况时，返回 0。当不满足情况，即要输出 No 时，返回 -1。
那么我们只需要在 dfs 过程中开一个数组记录一下每个 dfs 的返回值，然后再数一下数组中有多少个值不为 K，再跟上一个判断就行了。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int MAXN = 2e5+5;

int n, k;
vector<int> e[MAXN];

int dfs(int u, int fa)
{
    vector<int> siz;
    for(int i = e[u].size()-1;i >= 0;i--)
    {
        int v = e[u][i];
        if(v == fa) continue;
        int sz = dfs(v, u);
        if(sz) siz.push_back(sz);
        if(sz == -1) return -1;
    }
    int cnt = 0;
    int re = 0;
    vector<int> sta;//存的是长度不为 K 的链的长度
    for(int i = siz.size()-1;i >= 0;i--)
    {
        int sz = siz[i];
        if(sz != k)
        {
            sta.push_back(sz);
        }
    }
    if(sta.size() > 2)
    {
        return -1;
    }
    if(sta.size() == 1)
    {
        return sta[0]+1;
    }
    if(sta.size() == 2)
    {
        if(sta[0] + sta[1] + 1 != k) return -1;
        else return 0;
    }
    return 1;
  //最后记得要return 1（我就是这个 1 打成 0 了赛后4min才调出来）
}

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