@codeforces – [email protected] Vladislav and a Great Legend

@[emailprotected]

Give Determine a tree T with n points. For each non-empty point set X, define f(X) as the number of edges of the smallest connected block containing all points in X.
Given another positive integer k, find:
\[\sum\limits_{X \subseteq \{1, 2,\: \dots \:, n\ },\, X \neq \varnothing} (f(X))^k\]

Modulo 10^9 + 7.

Input
The first line of two integers n and k (2≤n≤10^5, 1≤k≤200), indicating the number of points and exponents.
In the next n lines, each line contains two integers ai, bi, describing a tree edge (1≤ai, bi≤n).
Output
Output an integer, representing the result mod 10^9 + 7.

Examples
Input
4 1
1 2
2 3
2 4
< strong>Output
21

Input
4 2
1 2
2 3
2 4
< strong>Output
45

Input
5 3
1 2
2 3
3 4
4 5
Output
780

@[email protected]

If we follow the usual thinking, we can An i counts the number of f(X) = i.
But I can only think of the O(n^2) approach, and there is no way to optimize it further.

When k = 1, we can think of how many Xs are counted for each edge so that the connected block corresponding to X contains this edge. This is easy to do.
When k ≠ 1, notice that the range of k is still small (k <= 200), why don’t we expand it analogy: for each edge set of size k, count how many Xs make X correspond to the connectedness The block contains this edge.
It seems that it cannot be easily compared.

Let’s consider a common routine, Stirling inversion:
\[m^k = \sum_{i=0}^{m} C(m, i)*S(k, i)*i!\]

where S represents the second kind of Stirling number. There are a lot of proofs on the Internet, so I won’t repeat them here.
Note that when i> k, S(k, i) = 0, so again \(m^k = \sum_{i=0}^{m}C( m, i)*S(k, i)*i!\).
So we rewrite the original formula:
\[\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})\]

We enumerate i, Then S(k, i)*i! can be calculated directly.
The meaning of the combination of the latter pile is actually “select an edge set of size i from the tree, how many connected blocks corresponding to the point set X contain this edge set”.
We have achieved our original goal.

We can count that thing through the tree dp.
For each point set X, we count the relevant information of this X at the LCA of all points in X.
Therefore, in order to facilitate the transfer, we define f[i][j] to mean that in the subtree rooted at i, the LCA of the point set X is higher than or equal to i, and the number of solutions with j edges has been selected.

When counting the schemes of selecting j edges when LCA is i, if a new subtree p is added, and the connected block formed by the previous subtree and root i is q, then the newly added scheme del is equal to Select the plan with a total of j edges for the connecting edges between p, q, p and root i.
After discussing it, you can transfer.
The transition of f is roughly similar to the above, but it should be noted that f may not select the point in p (that is, select an empty set in p). Need to be discussed separately.

It should be noted that in order to prevent the time complexity from degenerating to O(nk^2), we cannot directly enumerate to k, but should enumerate to min(size, k), where size is The size of the subtree. This complexity is O(nk).
This is actually an optimized routine of the general tree dp. However, the general tree dp proof only needs to know that each point pair will only be counted at the LCA, and this proof is more troublesome.

(The following is reproduced from this blog).

First consider a number of Consider the combination of Finally, two ≥k subtrees are merged. Since there are only at most n/k such subtrees, the number of operations does not exceed nk, so the complexity is O(nk).
So the final complexity is O(nk), and the key to reducing the complexity is that the cost of merging can be min with the size of the subtree.

@accepted [emailprotected]

#include#includeusing 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); }i nt 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
@[emailprotected]
 < p>So the tree dp is often a type that sounds easy and has a lot of code details. Look at the code to be easier to understand. . . 

Contents


@[email protected]
@[emailprotected]
@accepted [email protected]
@[email protected]



@[email protected]
@[email protected]
@accepted < span class="__cf_email__" data-cfemail="75161a111035">[email protected]
@[emailprotected]< /span>