#include <bits/stdc++.h>
using namespace std;
const int N = 1e4 + 10;
int n, k, h[N], dp[N];
vector<int> adj[N];
bool dfs(int u, int par) {
if (par == -1) h[u] = 0;
dp[u] = h[u];
vector<int> vec;
for (int v: adj[u])
if (v != par) {
h[v] = h[u] + 1;
if (!dfs(v, u)) return false;
dp[u] = max(dp[u], dp[v]);
vec.push_back(dp[v]);
}
if (vec.size() < 2 || h[u] % k == 0) return true;
int maxi = 0, maxi2 = 0;
for (int x: vec)
if (x > maxi2) {
maxi2 = x;
if (maxi2 > maxi)
swap(maxi, maxi2);
}
if (maxi2 >= h[u] + k - (h[u] % k) && 2 * (h[u] + k - (h[u] % k) - h[u]) < k) {
return false;
}
if (min(maxi, h[u] + k - (h[u] % k) - 1) - h[u] + min(maxi2, h[u] + k - (h[u] % k) - 1) - h[u] >= k - 1) {
return false;
}
return true;
}
void input() {
cin >> n >> k;
for (int i = 0; i < n - 1; i++) {
int u, v;
cin >> u >> v;
u--, v--;
adj[u].push_back(v);
adj[v].push_back(u);
}
}
void solve() {
for (int i = 0; i < n; i++) {
if (dfs(i, -1)) {
cout << "YES\n" << 1;
return;
}
}
cout << "NO\n" << 0;
}
int main() {
ios:: sync_with_stdio(0), cin.tie(0), cout.tie(0);
input();
solve();
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |