「COCI2016/2017 Contest #2」Bruza

解题思路 :

首先对于任意时刻 $i$ ，硬币一定移动到了深度为 $i$ 的节点，所以第 $i$ 时刻 Danel 一定染掉一个深度为 $i + 1$ 的节点。又因为如果硬币到了深度为 $k$ 的节点游戏就结束了，所以深度 $> k$ 的节点都可以忽视，把所有深度 $= k$ 的节点看做这棵树的叶子，如果一个节点其子树里面没有深度 $= k$ 的节点，那么这整棵子树也是可以被忽视的。

其次，如果染色的一个节点是另外一个节点的祖先，那么深度较深的那个节点被染是没有意义的。

那么每次染掉一个深度为 $i$ 的节点，其至少会使得 $k-i+1$ 个节点无法到达，那么染 $k$ 次能染掉的节点数量的下界就是：

\[\sum_{i=1}^k k - i + 1= k(k+1)-\frac{k(k+1)}{2}=\frac{k(k+1)}{2}
\]

于是可以得到一个关于 $k$ 的较松的上界，当满足时 Danel 必胜：

\[k \geq \sqrt{2n}
\]

实际上这个上界是比较松的，可以继续证明并加以利用。观察发现如果染掉一个没有分叉的节点，等价于染掉其子树中第一个有分叉的节点。那么可以除了根节点以外，每次染掉深度最小的一个有分叉的节点，且要保证任意时刻 $i$ ，染掉的深度 $\leq i$ 的节点个数必须 $\leq i $ 。

显然，如果每种深度的节点有分叉的仅有一个，那么Danel必胜。

假设在某一时刻出现两个深度最小为 $d$ 且有分叉的节点，那么其中一个有分叉的节点不能被染掉。相当于转化为进入这个节点所对应的子树的一个子问题，而在这之前，通过染色使得不能到达的最少节点数量之和是：

\[\sum_{i=1}^d 2k - i =2kd-\frac{d(d+1)}{2}
\]

解释一下这个式子，假设之前的被染色的每一个节点都只有两个分叉，且这两个分叉对应的子树都是以两条链的形式存在的，这样显然是最少的情况，此时被减少至不能再到达的部分就是该节点到根的路径以及这两个分叉。

令 $S(n, k)$ 为初始状态的规模，此时进入的子问题的规模是 $S(n', k')$ ，根据上述分析一下可以得到：

\[k' = k - d \\
n' = n - 2kd+\frac{d(d+1)}{2} \\
n' \leq n - 2kd + d^2
\]

在这里假设一个更小的上界使得当满足时 Danel 必胜：

\[k \geq \sqrt{n} \\
k^2 \geq n
\]

那么之前的式子

\[k' = k - d \\
n' \leq k^2 - 2kd + d^2 \\
n' \leq (k -d)^2
\]

此时 $S(n',k')$ 仍然满足假设的上界 $k \geq \sqrt{n}$ ，这里归纳证明得到了一个更小的上界当满足时 Danel 必胜。

把问题带回最初的贪心思路，第 $i$ 次选择深度为 $i+1$ 的节点一定是最优的，那么深度 $[2,k]$ 每种只能染最多一个节点，且最终要使得所有叶子都有一个祖先在染色的点集里面。

把问题转化到反dfn序上，令 $dp(i, s)$ 表示反dfn序前 $i$ 为已经选了深度集合为 $s$ 的点能覆盖的最多叶子数量，为了防止对叶子的贡献重复计数，同一子树内不能同时选，那么转移的时候讨论一下就好了

\[dp(i, s) =\max(dp(i-1,s), dp(i-sz[i],s-2^{dep[i]})+val[i])
\]

其中 $sz[i]$ 是反dfn序上第 $i$ 位对应的节点的大小，$val[i]$ 是这个节点的子树中的叶子节点数量，最后看一下是否存在一个 $dp$ 状态能覆盖所有叶子即可，总复杂度 $O(n2^\sqrt{n})$。

据说还有 $O(\sqrt{n}2^{\sqrt{n}})$ 的做法, 又据说一言难尽，改天再填坑吧。

code

/*program by mangoyang*/

#pragma GCC optimize("Ofast","inline","-ffast-math")

#pragma GCC target("avx,sse2,sse3,sse4,mmx")

#include<bits/stdc++.h>

#define inf (0x7f7f7f7f)

#define Max(a, b) ((a) > (b) ? (a) : (b))

#define Min(a, b) ((a) < (b) ? (a) : (b))

typedef long long ll;

using namespace std;

template <class T>

inline void read(T &x){

	int ch = 0, f = 0; x = 0;

	for(; !isdigit(ch); ch = getchar()) if(ch == '-') f = 1;

	for(; isdigit(ch); ch = getchar()) x = x * 10 + ch - 48;

	if(f) x = -x;

}

const int N = 405;

vector<int> g[N];

int f[N][(1<<17)+2], vi[N][(1<<17)+2];

int sz[N], d[N], dfn[N], mx[N], h[N], leaf, n, k, cnt, all, tot;

inline int MX(int x, int y){ return x > y ? x : y; }

inline int solve(int u, int s){

	if(~f[u][s]) return f[u][s];

	if(s == all || u > cnt) return f[u][s] = 0;

	if(u == 1 || (1 << d[u]) & s || mx[u] < k) return f[u][s] = solve(u + 1, s);

	return f[u][s] = MX(solve(u + sz[u], s | (1 << d[u])) + h[u], solve(u + 1, s));

}

inline void dfs(int u, int fa){

	dfn[u] = ++cnt; sz[dfn[u]] = 1;

	if(u > 1) d[dfn[u]] = d[dfn[fa]] + 1;

	mx[dfn[u]] = d[dfn[u]];

	if(d[dfn[u]] == k) return (void) (leaf++, h[dfn[u]] = 1);

	for(int i = 0; i < g[u].size(); i++){

		int v = g[u][i];

		if(v == fa) continue;

		dfs(v, u), sz[dfn[u]] += sz[dfn[v]], h[dfn[u]] += h[dfn[v]];

		mx[dfn[u]] = MX(mx[dfn[u]], mx[dfn[v]]);

	}

}

int main(){

	memset(f, -1, sizeof(f));

	read(n), read(k), all = (1 << k) - 1;

	if(k * k >= n) return puts("DA"), 0;

	for(int i = 1, x, y; i < n; i++){

		read(x), read(y);

		g[x].push_back(y), g[y].push_back(x);

	}

	dfs(1, 0);

	for(int i = 1; i <= n; i++) d[i]--;

	puts(solve(1, 0) >= leaf ? "DA" : "NE");

	return 0;

}

巴特西

「COCI2016/2017 Contest #2」Bruza