#include <bits/stdc++.h>
using namespace std;
const int INF=0x3f3f3f3f;
vector<int> adj[401];
int dep[401],dp[1<<19],l[401],r[401],curr,n,k;
void dfs(int v, int p){
if(dep[v]==k) {l[v]=r[v]=++curr; return; }
for(int u:adj[v]){
if(u==p) continue;
dep[u]=dep[v]+1; dfs(u,v);
l[v]=min(l[v],l[u]);
r[v]=max(r[v],r[u]);
}
}
int main(){
cin >>n>>k;
memset(l,INF,sizeof(l)); memset(r,0,sizeof(r));
if(k>=20) {cout <<"NE\n"; return 0;}
for(int i=1;i<n;i++){
int a,b; cin >>a>>b;
adj[a].push_back(b);
adj[b].push_back(a);
}dfs(1,-1);
for(int mask=1;mask<(1<<k);mask++){
dp[mask]=-INF;
for(int i=1;i<=n;i++){
if(!dep[i] || !(mask&(1<<(dep[i]-1)))) continue;
if(dp[mask^(1<<(dep[i]-1))]+1>=l[i]) dp[mask]=max({dp[mask],r[i],dp[mask^(1<<(dep[i]-1))]});
}
}cout <<(dp[(1<<k)-1]==curr?"DA":"NE");
}
# | 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... |
# | 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... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |