首先解释题意，对于既定策略，我们要求方案不随对方的移动而改变。

仔细思考，能取胜的最多点数的情况就是根节点下面有 $k$ 条长度为 $k$ 的链。因为对于长度小于 $k$ 的路径不需要考虑，而我们最多只能堵住 $k$ 条路径。

而这样恰好需要 $k$ 次才能全部堵住。

故得到推论 $n \leq k^2$ 时必胜。又 $n \leq 400$ 所以 $k \geq 20$ 时必胜。

这样我们只需要做 $k < 20$ 的部分。

同时我们只需要研究所有长度为 $k$ 的路径，其他的点我们可以全部舍弃。

通过上面的例子，我们容易发现第 $i$ 次标记的点深度为 $i$，即每一次按深度递增堵上一个子树。

我们考虑在 Dfn 序上做状压 DP 。

$f(i,s)$ 表示堵住了 Dfn 序大于 $i$ 的所有点，标记状态为 $s$ 的可行性。

对于深度不为 $k$ 的点，$f(i,s) = f(i+1,s)$，因为堵住了Dfn序大于 $i+1$ 的点，那么就堵住了 $i$ 的所有子树，那么这个点也没用了。

接着还有转移，堵上 $i$ 这个点，这会堵上 $i$ 的子树，从 $i + sz(i)$ 转移。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
#include<bits/stdc++.h>
using namespace std;
const int maxn=400;
const int maxm=1<<19;
struct Edge{int u,v,nxt;};
int n,K;
int hd[maxn+5],et;
Edge e[(maxn<<1)+5];
int de[maxn+5];
int sz[maxn+5];
bool flg[maxn+5];
int dfn[maxn+5],dfnt;
int to[maxn+5],rde[maxn+5];
bool f[maxn+5][maxm+5];
inline void Adde(int u,int v){
    e[et].u=u,e[et].v=v,e[et].nxt=hd[u],hd[u]=et++;
}
void Dfs1(int u,int fa){
    int v;
    sz[u]=1;
    if(de[u]==K) flg[u]=1;
    for(int i=hd[u];~i;i=e[i].nxt){
        v=e[i].v;
        if(v==fa) continue;
        de[v]=de[u]+1;
        Dfs1(v,u);
        sz[u]+=sz[v];
        flg[u]|=flg[v];
    }
}

void Dfs2(int u,int fa){
    int v;
    if(!flg[u]) return;
    dfn[u]=dfnt++;
    for(int i=hd[u];~i;i=e[i].nxt){
        v=e[i].v;
        if(v==fa) continue;
        Dfs2(v,u);
    }
    to[dfn[u]]=dfnt;
    rde[dfn[u]]=de[u]-1;
}
signed main(){
    int u,v;
    memset(hd,-1,sizeof(hd));
    scanf("%d%d",&n,&K);
    if(K>=20){puts("DA");return 0;}
    for(int i=1;i<n;i++){
        scanf("%d%d",&u,&v);
        Adde(u,v),Adde(v,u);
    }
    Dfs1(1,0);
    Dfs2(1,0);
    int tp=(1<<K)-1;
    memset(f[dfnt],1,sizeof(f[dfnt]));
    for(int i=dfnt-1;i>=1;i--){
        if(rde[i]<K-1)
            for(int j=0;j<=tp;j++)
                f[i][j]=f[i+1][j];
        for(int j=0;j<=tp;j++)
            if(j&(1<<rde[i]))
                f[i][j]|=f[to[i]][j^(1<<rde[i])];
    }
    puts(f[1][tp]?"DA":"NE");
    return 0; 
}