#include<bits/stdc++.h>
using namespace std;
const int N = 1.5e6 + 10, mod = 1e9+7;
int n, k;
vector<int> G[N];
bool done[N], mark[N];
int dfs(int v, int p = -1)
{
int ans = 0;
for(int u : G[v])
if(u != p)
ans = max(ans, 1 + dfs(u, v));
return ans;
}
int diameter()
{
int ans = 0;
for(int v = 1; v <= n; v ++)
ans = max(ans, dfs(v));
return ans;
}
bool Close;
void Dfs(int v, int p = -1, int d = 1)
{
if(Close || d >= k) return;
for(int u : G[v])
if(u != p)
{
if(mark[u] && d + 1 <= k)
{
// cerr << u << ' ' << d + 1 << endl;
Close = true;
}
Dfs(u, v, d + 1);
}
}
bool check(int v)
{
bool seen[n + 1] = {};
seen[v] = 1;
vector<int> level = {v};
int l = 0;
vector<int> vec;
Close = false;
while(level.size())
{
if(l == 1)
for(int v : level)
vec.push_back(v);
vector<int> nl;
for(int v : level)
{
int cnt = 0;
for(int u : G[v])
if(!seen[u])
cnt++, seen[u] = 1, nl.push_back(u);
if(l == k - 1 && cnt > 1)
Close = true;
}
l = l % k + 1;
level = nl;
}
for(int v : vec)
done[v] = mark[v] = true;
for(int i = 0; i < vec.size(); i ++)
Dfs(vec[i]);
for(int v : vec)
mark[v] = false;
return !Close;
}
int main()
{
cin >> n >> k;
if(k == 2)
{
cout << "YES\n";
cout << 2 << endl;
return 0;
}
for(int i = 1; i < n; i ++)
{
int a, b;
cin >> a >> b;
G[a].push_back(b);
G[b].push_back(a);
}
int x = diameter();
if(x + 1 < k)
{
cout << "YES\n";
int ans = 1;
for(int i = 0; i < n; i ++)
ans = (ans * 2) % mod;
cout << ans << endl;
return 0;
}
int ans = 0;
for(int v = 1; v <= n; v++)
if(!done[v])
ans += check(v);
cout << (ans == 0 ? "NO" : "YES") << endl;
cout << ans << endl;
return 0;
}
# | 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... |