Submission #63826130

Source Code Expand

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <bits/stdc++.h>
using namespace std;
#ifdef local
#include <debug.hpp>
#else
#define debug(...)
#endif
#define rep(i, n) for (int i = 0; i < n; i++)
template <class T> istream& operator>>(istream& I, vector<T>& V) {for (T& X : V) I >> X; return I;}
template <class T> inline bool chmax(T& a, T b) {if (a < b) {a = b; return true;} return false;}
template <class T> inline bool chmin(T& a, T b) {if (a > b) {a = b; return true;} return false;}
vector<int> di = {-1, 1, 0, 0}, dj = {0, 0, -1, 1}; int inf = 1e9; long INF = 1e18;
int main() {
    int n, k;
    cin >> n >> k;
    if (k == 1) {
        cout << "Yes\n";
        return 0;
    }
    n = n * k;
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

#include <bits/stdc++.h>
using namespace std;
#ifdef local
#include <debug.hpp>
#else
#define debug(...)
#endif
#define rep(i, n) for (int i = 0; i < n; i++)
template <class T> istream& operator>>(istream& I, vector<T>& V) {for (T& X : V) I >> X; return I;}
template <class T> inline bool chmax(T& a, T b) {if (a < b) {a = b; return true;} return false;}
template <class T> inline bool chmin(T& a, T b) {if (a > b) {a = b; return true;} return false;}
vector<int> di = {-1, 1, 0, 0}, dj = {0, 0, -1, 1}; int inf = 1e9; long INF = 1e18;

int main() {
    int n, k;
    cin >> n >> k;
    if (k == 1) {
        cout << "Yes\n";
        return 0;
    }
    n = n * k;
    vector<vector<int>> g(n);
    rep(i, n - 1) {
        int u, v;
        cin >> u >> v;
        u--; v--;
        g[u].push_back(v);
        g[v].push_back(u);
    }

    vector<int> dp(n, -inf), used(n);
    auto f = [&](auto f, int v, int p = -1) -> int {
        if (used[v]) return dp[v];
        used[v] = true;
        int cnt = 0, x = 0;
        for (int u : g[v]) if (u != p) {
            if (f(f, u, v) != 0) {
                cnt++;
                x = f(f, u, v);
            }
        }
        if (cnt >= 2) {
            return dp[v] = inf;
        } else if (cnt == 0) {
            return dp[v] = k - 1;
        } else {
            return dp[v] = x - 1;
        }
    };

    f(f, 0);

    vector<int> cnt(k);
    rep(i, n) if (dp[i] < k) cnt[dp[i]]++;
    rep(i, k) {
        if (cnt[i] != n / k) {
            cout << "No\n";
            return 0;
        }
    }

    assert(false);

    cout << (dp[0] ? "No\n" : "Yes\n");
    return 0;
}

Submission Info

Judge Result