【洛谷P6499】Burza

题目

题目链接：https://www.luogu.com.cn/problem/P6499
Daniel 和 Stjepan 在一棵含有 (n) 个节点的树上做游戏，树上各节点的编号为 (1,2,dots,n)。游戏开始时，(1) 号节点上有一枚硬币。
游戏规则如下：

Daniel 选择一个节点，将其标记。
Stjepan 标记当前硬币所在的节点。
Stjepan 将硬币移至一个尚未标记且与当前所在的节点相邻的节点。

重复以上操作。当 Stjepan 无法移动硬币时，游戏结束。
Daniel 想知道是否存在某种既定的操作策略，使得无论 Stjepan 如何操作，都能在 (k) 轮操作内结束游戏。即 Stjepan 能移动硬币的次数小于 (k)。

思路

可以发现后手操作 (i) 次之后一定在深度为 (i+1) 的节点处。所以我们可以直接忽略深度超过 (k) 的节点。并且第 (i) 次操作先手一定会选择深度为 (i+1) 的点，因为如果深度小于 (i+1)，后手已经走过这一层了；如果大于 (i+1)，不如选择它的父亲更优。
如果 (k^2>n)，那么 Daniel 必胜。因为最坏情况下一定是若干条长度为 (k) 的链，链顶端均与 (1) 相连。就算这样，它链的数量是 (lfloorfrac{n}{k} floor)，当 (k>lfloorfrac{n}{k} floor) 即 (k^2>n) 时一定先手必胜。
所以我们只需要解决 (k<sqrt{n}) 时的问题。由于先手每一个深度只会选择一次，所以我们可以设 (f[i][s]) 表示 dfs 序在 (isim n) 的节点都被选择时，我们选择深度的集合为 (s) 是否可行。
如果选择节点 (i)，那么有转移

[f[i][s]gets f[i+mathrm{size}_{mathrm{rk}_i}][s mathrm{xor} mathrm{dep}_{mathrm{rk}_i}] ]

如果不选择节点 (i)，只需要把 (i) 子树内深度为 (k) 的节点删掉就可以了。所以如果 (mathrm{dep}_ileq k)，

[f[i][s]gets f[i+1][s] ]

最后判断一下 (f[1][i]) 的或和是否为 (1) 即可。
时间复杂度 (O(2^{sqrt{n}}n))。

代码

#include <bits/stdc++.h>
using namespace std;

const int N=405,M=(1<<19);
int n,m,tot,lim,ans,head[N],dep[N],siz[N],dfn[N],rk[N];
bool f[N][M];

struct edge
{
	int next,to;
}e[N*2];

void add(int from,int to)
{
	e[++tot]=(edge){head[from],to};
	head[from]=tot;
}

void dfs(int x,int fa)
{
	dep[x]=dep[fa]+1;
	if (dep[x]>m+1) return;
	dfn[x]=++tot; rk[tot]=x; siz[x]=1;
	for (int i=head[x];~i;i=e[i].next)
	{
		int v=e[i].to;
		if (v!=fa)
		{
			dfs(v,x);
			siz[x]+=siz[v];
		}
	}
}

int main()
{
	memset(head,-1,sizeof(head));
	scanf("%d%d",&n,&m);
	if (m*m>n) return printf("DA"),0;
	for (int i=1,x,y;i<n;i++)
	{
		scanf("%d%d",&x,&y);
		add(x,y); add(y,x);
	}
	tot=0; dfs(1,0);
	f[n+1][0]=1; lim=(1<<m+1);
	for (int i=n;i>=2;i--)
		for (int s=0;s<lim;s++)
		{
			int j=rk[i];
			if (s&(1<<dep[j]-1))
				f[i][s]|=f[i+siz[j]][s^(1<<dep[j]-1)];
			if (dep[j]<=m)
				f[i][s]|=f[i+1][s];
		}
	for (int i=0;i<lim;i++)
		ans|=f[2][i];
	if (ans) printf("DA");
		else printf("NE");
	return 0;
}