#include "bits/stdc++.h"
using namespace std;
using ll = long long;
#define endl '\n'
#ifdef LOCAL
#include "debug.h"
#else
#define debug(...) 37
#endif
const int N = 203;
vector<vector<int> > g;
int n, k;
int dist[N][N];
vector<int> max_dist;
vector<bool> marked;
int dist_calc(const int source, int v, int p) {
dist[source][v] = dist[source][p] + 1;
pair<int, int> mx{0, 0};
for(int to : g[v]) {
if(to != p) {
dist_calc(source, to, v);
mx = max({mx, {mx.first, max_dist[to] + 1}, {max_dist[to] + 1, mx.first}});
}
}
max_dist[v] = mx.first;
return mx.first + mx.second;
}
bool check_dfs(int v, int p, int d) {
if(marked[v]) {
return true;
}
if(d + 1 >= k) {
return false;
}
bool ok = true;
for(int to : g[v]) {
if(to != p and !marked[to]) {
ok &= check_dfs(to, v, d + 1);
if(!ok) {
break;
}
}
}
return ok;
}
vector<int> mark_set(int x) {
vector<int> res;
marked.assign(n + 1, false);
for(int i = 1; i <= n; ++i) {
if(dist[x][i] % k == 0) {
marked[i] = true;
res.push_back(i);
}
}
return res;
}
const ll mod = 1e9 + 7;
inline void solve(){
memset(dist, -1, sizeof(dist));
cin >> n >> k;
if(n > 200) {
cout << "NO\n0\n";
return;
}
g.assign(n + 1, vector<int>());
for(int i = 1; i < n; ++i) {
int u, v;
cin >> u >> v;
g[u].push_back(v);
g[v].push_back(u);
}
vector<bool> useless(n + 1);
for(int i = 1; i <= n; ++i) {
max_dist.assign(n + 1, 0);
int len = dist_calc(i, i, 0);
if(len + 1 < k) {
useless[i] = true;
}
}
ll ans = 0;
if(count(useless.begin() + 1, useless.end(), true) == n) {
ans = 1;
for(int i = 1; i <= n; ++i) {
ans = ans * 2 % mod;
}
cout << "YES\n"
<< ans << '\n';
return;
}
for(int u = 1; u <= n; ++u) {
if(useless[u]) {
continue;
}
vector<int> marked_vertices = mark_set(u);
const int m = marked_vertices.size();
bool ok = true;
for(int i = 0; i < m; ++i) {
if(marked_vertices[i] < u) {
ok = false;
break;
}
for(int j = 0; j < i; ++j) {
if(dist[marked_vertices[i]][marked_vertices[j]] % k) {
ok = false;
break;
}
}
if(!ok) {
break;
}
}
for(int i = 1; i <= n; ++i) {
if(!marked[i] and !check_dfs(i, -1, 0)) {
assert(false);
break;
}
}
debug(u, ok);
ans += ok;
}
for(int i = 1; i <= n; ++i) {
if(useless[i]) {
ans = ans * 2 % mod;
}
}
cout << (ans ? "YES\n" : "NO\n") << ans << endl;
}
signed main(){
#ifdef LOCAL
freopen("test.in", "r", stdin);
freopen("err.txt", "w", stderr);
#endif
ios_base::sync_with_stdio(0);
cin.tie(NULL);
// signed t; cin >> t; while(t--)
solve();
}
Compilation message
wells.cpp: In function 'void solve()':
wells.cpp:9:20: warning: statement has no effect [-Wunused-value]
9 | #define debug(...) 37
| ^~
wells.cpp:124:9: note: in expansion of macro 'debug'
124 | debug(u, ok);
| ^~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
604 KB |
Output is correct |
| 2 |
Runtime error |
1 ms |
860 KB |
Execution killed with signal 6 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
604 KB |
Output is correct |
| 2 |
Runtime error |
1 ms |
860 KB |
Execution killed with signal 6 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
604 KB |
Output is correct |
| 2 |
Runtime error |
1 ms |
860 KB |
Execution killed with signal 6 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
604 KB |
Output is correct |
| 2 |
Runtime error |
1 ms |
860 KB |
Execution killed with signal 6 |
| 3 |
Halted |
0 ms |
0 KB |
- |
