#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
typedef long long ll;
void speed()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
}
const int maxn = 1e4 + 10;
int n, k;
vector < int > adj[maxn];
void input()
{
cin >> n >> k;
for (int i = 1; i < n; i ++)
{
int v, u;
cin >> v >> u;
adj[v].push_back(u);
adj[u].push_back(v);
}
}
int used[maxn];
void bfs(int s)
{
for (int i = 1; i <= n; i ++)
used[i] = 0;
queue < int > q;
q.push(s);
used[s] = 1;
while(!q.empty())
{
int v = q.front();
q.pop();
for (int u : adj[v])
{
if (used[u] == 0)
{
used[u] = used[v] + 1;
q.push(u);
}
}
}
}
int tin[maxn], ord[2 * maxn], timer;
int depth[maxn];
void dfs(int v, int p)
{
ord[ ++ timer] = v;
tin[v] = timer;
for (int u : adj[v])
{
if (u == p)
continue;
depth[u] = depth[v] + 1;
dfs(u, v);
ord[++ timer] = v;
}
}
const int maxlog = 23;
int dp[maxlog][2 * maxn], lg[2 * maxn];
void build_sparse_table()
{
for (int i = 1; i <= timer; i ++)
{
lg[i] = lg[i / 2] + 1;
dp[0][i] = ord[i];
}
for (int j = 1; j < lg[timer]; j ++)
{
for (int i = 1; i <= timer - (1 << j) + 1; i ++)
{
dp[j][i] = dp[j - 1][i + (1 << (j - 1))];
if (depth[dp[j - 1][i]] < depth[dp[j][i]])
dp[j][i] = dp[j - 1][i];
}
}
/** for (int j = 0; j < lg[timer]; j ++, cout << endl)
for (int i = 1; i <= timer - (1 << j) + 1; i ++)
cout << dp[j][i] << " ";*/
}
int lca(int v, int u)
{
int l = tin[v], r = tin[u];
if (l > r) swap(l, r);
int len = lg[r - l + 1] - 1;
int lca = dp[len][r - (1 << len) + 1];
if (depth[dp[len][l]] < depth[lca])
lca = dp[len][l];
return lca;
}
int dist(int v, int u)
{
return depth[v] + depth[u] - 2 * depth[lca(v, u)];
}
int path[maxn][maxn];
void find_path()
{
for (int i = 1; i <= n; i ++)
{
bfs(i);
for (int j = 1; j <= n; j ++)
path[i][j] = used[j] - 1;
}
}
vector < int > st;
void check()
{
for (int s = 1; s <= n; s ++)
{
bfs(s);
for (int i = 1; i <= n; i ++)
{
if (used[i] % k == 1)
st.push_back(i);
}
bool done = true;
for (int v : st)
{
if (!done)
break;
for (int u : st)
{
if (dist(v, u) < k)
{
///cout << "dist " << lca(v, u) << " " << v << " " << u << endl;
done = false;
break;
}
}
}
if (done)
{
cout << "YES" << endl;
cout << 0 << endl;
return;
}
}
cout << "NO" << endl;
cout << 0 << endl;
}
void solve()
{
input();
dfs(1, -1);
build_sparse_table();
///find_path();
///cout << dist(2, 6) << endl;
check();
}
int main()
{
speed();
solve();
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
600 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
600 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
600 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
600 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
