目录
- @[email protected]
- @[email protected]
- @accepted [email protected]
- @[email protected]
@[email protected]
给定一棵 n 个点的树 T。对于每一个非空点集 X，定义 f(X) 为包含 X 内所有点的最小连通块的边数。
另给定一正整数 k，求：
\[\sum\limits_{X \subseteq \{1, 2,\: \dots \:, n\},\, X \neq \varnothing} (f(X))^k\]
模 10^9 + 7。
Input
第一行两个整数 n 与 k (2≤n≤10^5, 1≤k≤200)，表示点数及指数。
接下来 n 行每行两个整数 ai, bi，描述一条树边 (1≤ai, bi≤n)。
Output
输出一个整数，表示结果 mod 10^9 + 7。
Examples
Input
4 1
1 2
2 3
2 4
Output
21
Input
4 2
1 2
2 3
2 4
Output
45
Input
5 3
1 2
2 3
3 4
4 5
Output
780
@[email protected]
如果以平常的思路，我们可以对于每一个 i 统计 f(X) = i 的个数。
但是我只能想到 O(n^2) 的做法，没办法进一步优化。
当 k = 1 时，我们可以想到对于每一条边，统计有多少 X 使得 X 对应的连通块包含这条边。这是很容易办到的。
当 k ≠ 1 时，注意到 k 的范围依然较小 (k <= 200) ，我们为什么不类比拓展一下：对于每个大小为 k 的边集，统计有多少 X 使得 X 对应的连通块包含这条边。
看起来好像不能够这样轻易类比。
我们考虑一个常见的套路，即斯特林反演：
\[m^k = \sum_{i=0}^{m}C(m, i)*S(k, i)*i!\]
其中 S 表示第二类斯特林数。这个证明网上挺多的，不再赘述。
注意到当 i > k 时 S(k, i) = 0，所以又有 \(m^k = \sum_{i=0}^{m}C(m, i)*S(k, i)*i!\)。
于是我们改写原式：
\[\sum\limits_{X \subseteq \{1, 2,\: \dots \:, n\},\, X \neq \varnothing} (f(X))^k = \sum_{i=0}^{k}S(k, i)*i!*(\sum\limits_{X \subseteq \{1, 2,\: \dots \:, n\},\, X \neq \varnothing} C_{f(X)}^{i})\]
我们枚举 i，则 S(k, i)*i! 可以直接算。
后面那一堆的组合意义实际上是 “从树上选出一个大小为 i 的边集，有多少点集 X 对应的连通块包含这个边集”。
我们就实现了我们最初的目的。
我们可以通过树形 dp 来统计那个东西。
对于每个点集 X，我们在 X 内所有点的 LCA 处统计这个 X 的相关信息。
因此为了方便转移，我们定义 f[i][j] 表示以 i 为根的子树中，点集 X 的 LCA 高于或等于 i，已经选中 j 条边的方案数。
统计 LCA 为 i 时选出 j 条边的方案时，如果新加进来一个子树 p，以前的子树与根 i 构成连通块为 q，则新增的方案 del 等于 p 中、 q 中、p 与根 i 之间的连边选中共 j 条边的方案。
讨论一下就可以转移了。
f 的转移与上面大致相似，不过需要注意的是，f 可能会不选 p 中的点（即对应在 p 中选个空集）。需要单独拿出来讨论。
需要注意的是，为了不让时间复杂度退化成 O(nk^2)，我们不能直接枚举到 k，而应该枚举到 min(size, k)，其中 size 是子树的大小。这样复杂度是 O(nk)。
这个其实是一般的树形 dp 的一个优化的套路。不过一般的树形 dp 的证明只需要知道每个点对只会在 LCA 处统计即可得证，而这个证明要麻烦一些。
（以下转载自这一篇博客）。
首先考虑若干个 <k 的子树进行合并直到合并为一个 ≥k 的子树，代价是O(k^2)的，最多合并成n/k个这样的，于是复杂度是O(nk)。
再考虑<k的与≥k的合并，复杂度是O(size?k)的，那么由于每一点最多经历一次这个过程，复杂度也是O(nk)。
最后是两个≥k的子树合并，由于只有最多n/k个这样的子树因此操作次数不超过nk，因此复杂度是O(nk)。
于是最终的复杂度是O(nk)，降低复杂度的关键是合并的代价可以和子树大小取min。
@accepted [email protected]
#include<cstdio>
#include<algorithm>
using namespace std;
const int MAXN = 100000;
const int MAXK = 200;
const int MOD = int(1E9) + 7;
inline int add(int a, int b) {return (a + b)%MOD;}
inline int mul(int a, int b) {return 1LL*a*b%MOD;}
struct edge{
int to; edge *nxt;
}edges[2*MAXN + 5], *adj[MAXN + 5], *ecnt = &edges[0];
void addedge(int u, int v) {
edge *p = (++ecnt);
p->to = v, p->nxt = adj[u], adj[u] = p;
p = (++ecnt);
p->to = u, p->nxt = adj[v], adj[v] = p;
}
int n, k;
int res[MAXK + 5], fct[MAXK + 5], S[MAXK + 5][MAXK + 5];
int func() {
int ans = 0;
for(int i=0;i<=k;i++)
ans = add(ans, mul(mul(S[k][i], fct[i]), res[i]));
return ans;
}
void init() {
S[0][0] = 1;
for(int i=1;i<=k;i++) {
S[i][0] = 0;
for(int j=1;j<=i;j++)
S[i][j] = add(S[i-1][j-1], mul(S[i-1][j], j));
}
fct[0] = 1;
for(int i=1;i<=k;i++)
fct[i] = mul(fct[i-1], i);
}
int f[MAXK + 5][MAXN + 5], siz[MAXN + 5];
void dfs(int x, int fa) {
f[0][x] = 1, res[0] = add(res[0], 1), siz[x] = 1;
for(edge *p=adj[x];p;p=p->nxt) {
if( p->to == fa ) continue;
dfs(p->to, x);
int t1 = min(siz[p->to] - 1, k), t2 = min(siz[x] - 1, k), t3 = min(siz[p->to] + siz[x] - 1, k);
for(int i=t2;i>=0;i--)
for(int j=min(t3-i, t1);j>=0;j--) {
int del = mul(f[i][x], f[j][p->to]);
res[i+j] = add(res[i+j], del), f[i+j][x] = add(f[i+j][x], del);
if( i+j+1 <= t3 )
res[i+j+1] = add(res[i+j+1], del), f[i+j+1][x] = add(f[i+j+1][x], del);
}
for(int i=0;i<=t1;i++) {
f[i][x] = add(f[i][x], f[i][p->to]);
if( i + 1 <= t3 )
f[i + 1][x] = add(f[i + 1][x], f[i][p->to]);
}
siz[x] += siz[p->to];
}
}
int main() {
scanf("%d%d", &n, &k), init();
for(int i=1;i<n;i++) {
int a, b; scanf("%d%d", &a, &b);
addedge(a, b);
}
dfs(1, 0);
printf("%d\n", func());
}
@[email protected]
所以树形 dp 往往是听上去容易，代码细节很多的类型。 看代码要容易理解一些吧。。。