#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) {
dp[u] = h[u];
if (par == -1) h[u] = 0;
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) return true;
int maxi = 0, maxi2 = 0;
for (int x: vec)
if (x > maxi2) {
maxi2 = x;
if (maxi2 > maxi)
swap(maxi, maxi2);
}
if (h[u] % k) {
if (maxi2 >= h[u] + k - (h[u] % k) && 2 * (h[u] + k - (h[u] % k)) < k - 1) {
// cout << u << ' ' << 111111111111111 << '\n';
return false;
}
if (min(maxi, h[u] + k - (h[u] % k) - 1) + min(maxi2, h[u] + k - (h[u] % k) - 1) >= k) {
// cout << u << ' ' << 2222222222222 << '\n';
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() {
cout << "YES\n" << 1;
return;
for (int i = 0; i < n; i++) {
// cout << i << ' ' << dfs(i, -1) << '\n';
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... |