COCI2016-2017 Contest#2 F

首先分析题意: 任意走都能在$k$步内结束，也就是说，一定可以在$k$步内封锁所有出路

注意游戏停止的条件是后手不能走，因此即使在$k$步封住了出路，下一轮依然要标记一个点

因此必须是$<k$的

设树根1的$dep=0$，第$i$层表示所有$dep=i$的节点

发现第$i$次操作，一定是从$i-1$层走到了$i$

假设最后的封路决策在$i$层封掉了2个点，那么这个决策一定是不优的

因为在$i$层花2的时间一定不如在$i-1$层和$i$层各花1的时间

因此，问题可以转化为: 在$1-k$层每层选择一个点，判断是否存在一种方案使得选择完成后完全封死出路

显然在最优情况下，选择的点之间不会有祖先关系，并且我们可以删掉所有$dep>k$的点

因此可以写出一个$n\cdot 2^k$的$dp$

由于最后要阻塞其实是阻塞所有的叶子($dep=k$的点)

因此考虑令选择每个节点是覆盖了一段叶子，将叶子按照$\text{dfs}$序从小到大依次标号，设选择$i$子树能覆盖叶子范围$L_i,R_i$

因此按照$L_i$从小到大依次考虑每个节点，加入的转移就是

$\begin{aligned} dep_i\notin S,dp_{L_i,S}\rightarrow dp_{R_i+1,S\cup \lbrace dep_i\rbrace }\end{aligned} $

如果用bitset实现，时间/空间复杂度均为$O(n \cdot 2^{k-5})$

如果直接$dp$显然。。。考虑缩小$k$的范围

推论1: 当$n< \frac{(k-1)\cdot (k+2)} {2}$时，一定有解

考虑一个浅显的贪心： 在第$i$层用$\leq i$的代价标记这层所有点

这个方法不可用的条件就是第$i$层的点个数$>i$，那么就有$n\ge 2+3+\cdots+k=\frac{(k-1)(k+2)} {2}$

可以看到此时$k$的上界已经缩小到$O(\sqrt n)$级别，但由于实际常数，还是太大了

推论2: 当$n\leq k\cdot k$时，一定有解

假设删除原树的1节点，则我们决策的对象变为一片森林

考虑依次决策每一层，每次推进一层，都会把选择一棵树删除，并且当前森林所有顶端的节点删除

要求$k$次决策后森林为空

设森林第一层包含$d$个节点

此时一定存在一个子树大小$\ge \frac{n} {d}$

删除这个子树后，规模变为$n-d-\frac{n} {d}+1$

我们知道$d+\frac{n} {d}\ge 2\sqrt n$

$n-d-\frac{n} {d}+1\leq n-2\sqrt n+1=(\sqrt n-1)^2$

因此得证

此时$k$的上界已经缩小到19，完全可以通过

带入优化的复杂度为$O(n\cdot 2^{15})$

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
#include<bits/stdc++.h>

using namespace std;
#pragma GCC optimize(2)
typedef long long ll;
#define reg register
#define pb push_back
#define rep(i,a,b) for(int i=a,i##end=b;i<=i##end;++i)
#define drep(i,a,b) for(int i=a,i##end=b;i>=i##end;--i)

char IO;
int rd(){
	int s=0;
	while(!isdigit(IO=getchar()));
	do s=(s<<1)+(s<<3)+(IO^'0');
	while(isdigit(IO=getchar()));
	return s;
}

const int N=410;

int n,m;
vector <int> G[N],Q[N];
int dep[N],L[N],R[N],cnt;

void pre_dfs(int u,int f) {
	dep[u]=dep[f]+1;
	if(dep[u]==m-1) { L[u]=cnt++,R[u]=cnt; return; }
	L[u]=cnt;
	for(int v:G[u]) if(v!=f) pre_dfs(v,u);
	R[u]=cnt;
}

bitset <1<<19> dp[401],rev[20];
int F[N]; 

int main(){
	n=rd(),m=rd();
	if(m*m>=n) return puts("DA"),0;
	rep(i,2,n) {
		int u=rd(),v=rd();
		G[u].pb(v),G[v].pb(u);
	}
	memset(dep,-1,sizeof dep),dep[0]=-2,pre_dfs(1,0);
	rep(i,1,n) if(~dep[i]) Q[L[i]].pb(i);
	dp[0][0]=1;
	rep(i,0,m-1) rep(j,0,(1<<m)-1) if(~j&(1<<i)) rev[i][j]=1;
	rep(i,0,cnt-1) 
		for(int v:Q[i]) {
			dp[R[v]]|=(dp[i]&rev[dep[v]])<<(1<<dep[v]);
		}
	puts(dp[cnt].count()?"DA":"NE");
}