JZOJ 5041 游戏

显然的是，若对于打叉的点，其深度互不相同，且在 [1,k] 内（假定根结点深度为 0），答案不会劣于最优解。
这是因为给两个同深度的点打叉几乎是毫无意义的……

易知最坏情况一定是从根伸展出若干条长度平均的链。
故问题转化为 k<20 的情况。
考虑标记所有深度为 k 的点，删去所有深度超过 k 和子树内没有标记点的点，那么问题转化为选定至多 k 个深度互不相同的点使得以这些点为根的子树的点集的并包含所有标记点。

由于要求子树并集包含所有标记点（容易发现在此时的树上，标记点即为全体叶子结点），可以考虑按照 DFS 序 DP。
设 fi,S 表示是否存在合法方案，满足覆盖了 DFS 序在 [1,i) 内的标记点，使用的深度构成集合 S。
有两种转移：

• 若 DFS 序排名为 i 的结点的父亲为 DFS 序排名为 i+1 的结点，则从 fi,S 转移到 fi+1,S；
• 若 i>1，则从 fi,S 转移到 fi+sizei,S∪{depthi}，其中 sizei,depthi 分别表示以 DFS 序排名为 i 的结点为根的子树大小、DFS 序排名为 i 的结点的深度。

时间复杂度 {O(n2k),k≤19O(1),k>19

代码：

#include <cstdio>
#include <vector>
#define lowbit(x) ((x) & -(x))
using namespace std;
const int N = 400;
const int K = 19;
const int ST = 92378;
int n,k,full;
int to[(N << 1) + 5],pre[(N << 1) + 5],first[N + 5];
int cnt[(1 << K) + 5],num[(1 << K) + 5];
vector<int> s[K + 5];
int f[2][N + 5][ST + 5],ans;
inline void add(int u,int v)
{
    static int tot = 0;
    to[++tot] = v,pre[tot] = first[u],first[u] = tot;
}
int fa[N + 5],dep[N + 5],sz[N + 5],flag[N + 5],id[N + 5],rk[N + 5],tot;
void dfs1(int p)
{
    flag[p] = dep[p] == k;
    for(register int i = first[p];i;i = pre[i])
        if(to[i] ^ fa[p])
            fa[to[i]] = p,dep[to[i]] = dep[p] + 1,dep[to[i]] <= k && (dfs1(to[i]),1),flag[p] |= flag[to[i]];
}
void dfs2(int p)
{
    rk[id[p] = ++tot] = p,sz[p] = 1;
    for(register int i = first[p];i;i = pre[i])
        if((to[i] ^ fa[p]) && flag[to[i]])
            dfs2(to[i]),sz[p] += sz[to[i]];
}
int main()
{
    freopen("game.in","r",stdin),freopen("game.out","w",stdout);
    scanf("%d%d",&n,&k);
    if(k >= 20)
    {
        puts("DA");
        return 0;
    }
    full = (1 << k) - 1;
    int u,v;
    for(register int i = 2;i <= n;++i)
        scanf("%d%d",&u,&v),add(u,v),add(v,u);
    dfs1(1),dfs2(1);
    s[0].push_back(0),f[0][1][0] = 1;
    for(register int i = 1;i <= full;++i)
        cnt[i] = cnt[i ^ lowbit(i)] + 1,
        num[i] = s[cnt[i]].size(),
        s[cnt[i]].push_back(i);
    for(register int c = 1,S;c <= k;++c)
    {
        for(register int i = 1;i <= tot + 1;++i)
            for(register int j = 0;j < s[c].size();++j)
                f[1][i][j] = 0;
        for(register vector<int>::iterator it = s[c - 1].begin();it != s[c - 1].end();++it)
        {
            S = *it;
            for(register int i = 1;i <= tot;++i)
                if(f[0][i][num[S]])
                    rk[i] == fa[rk[i + 1]] && (f[0][i + 1][num[S]] |= 1),
                    i > 1 && !(S & (1 << dep[rk[i]] - 1)) && (f[1][i + sz[rk[i]]][num[S | (1 << dep[rk[i]] - 1)]] |= 1);
        }
        for(register int i = 0;i < s[c].size();++i)
            ans |= f[1][tot + 1][i];
        for(register int i = 1;i <= tot;++i)
            for(register int j = 0;j < s[c].size();++j)
                f[0][i][j] = f[1][i][j];
    }
    puts(ans ? "DA" : "NE");
}