Multihedgehog

Created by LXC on Wed Feb 7 20:00:41 2024

https://codeforces.com/problemset/problem/1067/B

ranting: 1800

tag: dfs and similar, graphs, shortest paths

problem

定义一棵树 k-multihedgehog：

对于 1-multihedgehog，其中一个点度数 $\ge3$ ，其它点度数均为 $1$.

k-multihedgehog 是在 k-1-multihedgehog 的基础上，把所有度为 $1$ 的点替换成一个 1-multihedgehog 并与原图相连。

给出一颗树以及一个数k，问是否为k-multihedgehog。

solution

先从任意叶子s开始dfs，得到所有节点到s的距离。然后找最远的一个节点t，再次dfs，得到所有节点到t的距离。

我们知道一个合法的k-multihedgehog，其中心节点应该到叶子节点距离为k且只有一个这样的节点，所以我们找距离s和距离t都为k的节点。如果有多个这样的节点那么无解，只有一个这样的节点则进一步验证是否为k-multihedgehog。设这个节点为u，我们从u开始dfs并记录层数，设u节点为0层，那么叶子节点就应该在第k层。另外u至少有3个度，非u且非叶子节点至少有4个度。

code

#include <bits/stdc++.h>
#define SINGLE_INPUT
#define ll long long
#define ull unsigned long long
#define N 500005
#define MOD 998244353
using namespace std;

template<class t,class u> ostream& operator<<(ostream& os,const pair<t,u>& p) {
    return os<<'['<<p.first<<", "<<p.second<<']';
}
template<class t> ostream& operator<<(ostream& os,const vector<t>& v) {
    os<<'['; int s = 1;
    for(auto e:v) { if (s) s = 0; else os << ", "; os << e; }
    return os<<']';
}
template<class t,class u> ostream& operator<<(ostream& os,const map<t,u>& mp){
    os<<'{'; int s = 1;
    for(auto [x,y]:mp) { if (s) s = 0; else os << ", "; os<<x<<": "<<y; }
    return os<<'}';
}

void sol() {
    int n, k;
    cin >> n >> k;
    if (n<4) {
        cout << "No\n";
        return ;
    }
    vector<vector<int>> g(n+1);
    for (int i=1; i<n; i++) {
        int x, y;
        cin >> x >> y;
        g[x].push_back(y);
        g[y].push_back(x);
    }
    int s = -1;
    for (int i=1; i<=n; i++) {
        if (g[i].size() == 1) s = i;
    }
    vector<vector<int>> dis(2, vector<int>(n+1, -1));
    function<void(int,int,int)> dfs = [&](int x, int v, int o) {
        dis[o][x] = v;
        for (int y:g[x]) {
            if (dis[o][y] == -1) {
                dfs(y, v+1, o);
            }
        }
    };
    dfs(s, 0, 0);
    int d = 1;
    for (int i=1; i<=n; i++) {
        if (dis[0][i] > dis[0][d]) d = i;
    }
    dfs(d, 0, 1);

    vector<int> t;
    for (int i=1; i<=n; i++) {
        if (dis[0][i] == k && dis[1][i] == k) t.push_back(i);
    }
    // cout << t << endl;
    if (t.size() != 1) {
        cout << "No\n";
        return ;
    }
    function<bool(int,int,int)> check = [&](int x, int fa, int lev) {
        if (lev == k) {
            return g[x].size() == 1;
        }
        if (g[x].size() == 1) {
            return lev == k;
        }
        if (!lev && g[x].size() < 3) return false;
        if (lev && g[x].size() < 4) return false;
        for (auto y:g[x]) {
            if (y == fa) continue;
            if (!check(y, x, lev+1)) return false;
        }
        return true;
    };
    cout << (check(t[0], -1, 0)?"Yes\n":"No\n");
}

int main() {
    cout << setprecision(15) << fixed;
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
#ifndef SINGLE_INPUT
    int t;
    cin >> t;
    while (t--) {
        sol();
    }
#else
    sol();
#endif
    return 0;
}