Submission #65722734

---

Source Code Expand

#include <bits/stdc++.h>
#include <bits/extc++.h>
using namespace std;
using namespace __gnu_pbds;
const int N = 1e6 + 10, mod = 998244353;
typedef long long ll;
typedef pair<int, int> pii;
template<typename T>
void dbg(const T &t) { cerr << t << endl; }
template<typename Type, typename... Types>
void dbg(const Type& arg, const Types&... args) {
    #ifdef ONLINE_JUDGE
        return ;
    #endif
    cerr << arg << ' ';
    dbg(args...);
}   
mt19937 rnd(19937);
int n, k;
vector<int>e[N];
void Fail() { 
    cout << "No\n";
    exit(0);
}
inline int dfs(int u, int fa) {
    vector<int>c;
    for (auto v : e[u]) if (v != fa) {
        int x = dfs(v, u);
        if (x != -1) c.push_back(x + 1);
    }
    sort(c.begin(), c.end());
    if (c.size() > 1) {
        if (c.size() == 2 && c[0] + c[1] == k - 1) return -1;
        Fail();
    }
    if (c.size() == 1) {
        if (c[0] == k - 1) return -1;
        return c[0];
    }
    return 0;
}
int main() {
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    cin >> n >> k;
    for (int i = 1; i < n * k; i++) {
        int u, v;
        cin >> u >> v;
        e[u].push_back(v); e[v].push_back(u);
    }
    cout << ((dfs(1, 0) == -1 || k == 1) ? "Yes\n" : "No\n");
    return 0;
}

Submission Info

Judge Result