题解 P6499 【[COCI2016-2017#2] Burza】

· · 题解

偏思维的状压 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;
}