自动搬运

查看原文

来自洛谷，原作者为

	panyf **

搬运于2025-08-24 22:21:22，当前版本为作者最后更新于2020-05-01 20:05:17，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

偏思维的状压 dp 。

不要被数据范围吓到，当 $k>19$ 时直接输出 DA 就行，以下是简要证明：

首先，删掉所有深度大于 $k$ 的点（假设根节点深度为 $0$ ）。删掉所有子树内不存在深度等于 $k$ 的点的点，因为如果 Stjepan 走到这些点就不可能取胜了。

注意到 Daniel 第 $i$ 次标记的点深度必须大于等于 $i$ ，否则这次标记就是无效的。一个显然的贪心策略就是第 $i$ 次标记一个深度等于 $i$ 的点，这样能够堵住尽可能多的点。

考虑最坏的情况，就是根节点下面连了 $k$ 条长度为 $k$ 的链，此时只需每次堵住一条链， $k$ 次恰好能堵住所有的链，而此时 $n=k\times k+1$ 。所以只有 $n>k\times k+1$ 时 Stjepan 才可能获胜。此时如果 $k>19$ ，那么 $n>k\times k+1>400$ ，不符合题意。

对于其他的情况，每次堵住当前最大的子树，如果这棵子树已经变成一条链，那么转换为之前的情况，否则堵住的点数肯定多于之前的情况。所以只要 $k>19$ 那么 Daniel 必胜。

现在数据范围已经被大幅缩小，只需要 $O(n2^k)$ 的复杂度即可通过本题（常数很小，最慢点也就 100 多 ms ）。很容易想到状压 dp 。

根据 dfs 序的性质， 每一棵子树可以用 dfs 序上一段区间表示。那么我们预处理出 dfs 序。设 $f[i][j]$ 表示标记了深度状压后为 $j$ 的点，是否可以堵住 dfs 序在 $i$ 以后的点。

设 $sz[i]$ 为 $i$ 的子树大小， $g[i]=f[i]+sz[i]$ ，那么 $i$ 的子树即为 $i$ 到 $g[i]-1$ 中的所有点， $f[i]$ 就可以用 $f[g[i]]$ 来转移，因为只要堵住了 $g[i]$ 以后的点和点 $i$ ，那么 $i$ 子树中的点也被堵住了， $i$ 以后的点就都被堵住了。

当 $i$ 的深度小于 $k$ 时， $f[i]$ 还可以直接继承 $f[i+1]$ ，因为如果堵住了 $i+1$ 以后的点，就堵住了 $i$ 子树中除自身外所有点，点 $i$ 也没用了。

具体转移方程和细节见代码。

#include<bits/stdc++.h>
using namespace std;
const int N=403;
bool b[N],f[N][525003];
int he[N],to[N*2],ne[N*2],fa[N],g[N],d[N],p[N],id;
void dfs1(int x,int y){//预处理父亲和深度
	fa[x]=y,d[x]=d[y]+1;
	for(int i=he[x],j;i;i=ne[i])if((j=to[i])!=y)dfs1(j,x);
}
void dfs2(int x,int y,int z){//预处理dfs序
	for(int i=he[x],j;i;i=ne[i])if((j=to[i])!=y&&b[j])dfs2(j,x,++id);
	g[z]=id,p[z]=d[x];
}
int main(){
	int n,k,u,i,j,l,v,t=0;
	scanf("%d%d",&n,&k),u=1<<k,d[0]=-1;
	if(k>19)return puts("DA"),0;
	for(i=1;i<n;++i){
		scanf("%d%d",&j,&l);
		ne[++t]=he[j],to[t]=l,he[j]=t;
		ne[++t]=he[l],to[t]=j,he[l]=t;
	}
	dfs1(1,0);
	for(i=1;i<=n;++i)if(d[j=i]==k)do b[j]=1;while(j=fa[j]);//标记有用点
	dfs2(1,0,0),memset(f[id+1],1,u);
	for(i=id;i;--i){
		if(g[i]>i)memcpy(f[i],f[i+1],u);
		for(j=0,l=g[i]+1,v=1<<p[i]-1;j<u;++j)if(!(j&v))f[i][j|v]|=f[l][j];
	}
	puts(f[1][u-1]?"DA":"NE");
	return 0;
}