[关闭]
@oujunsong 2023-05-04T17:19:14.000000Z 字数 1156 阅读 129
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define int long long
  4. const int N = 1e5 + 5, mod = 1e9 + 7;
  5. int n, m, k, x, dp[N][11][3], tmp[11][3];
  6. int en, first[N], sz[N];
  7. struct edge {
  8. int e, next;
  9. }ed[N * 2];
  10. void add_edge(int s, int e) {
  11. en++;
  12. ed[en].e = e;
  13. ed[en].next = first[s];
  14. first[s] = en;
  15. }
  16. void init(int u, int fa) { // 预处理子树大小
  17. sz[u] = 1;
  18. for (int p = first[u]; p; p = ed[p].next) {
  19. int e = ed[p].e;
  20. if (e == fa) continue;
  21. init(e, u);
  22. sz[u] += sz[e];
  23. }
  24. }
  25. void dfs(int u, int fa) {
  26. dp[u][0][0] = k - 1;
  27. dp[u][1][1] = 1;
  28. dp[u][0][2] = m - k;
  29. for (int p = first[u]; p; p = ed[p].next) {
  30. int e = ed[p].e;
  31. if (e == fa) continue;
  32. dfs(e, u);
  33. for (int j = 0; j <= x; j++) {
  34. for (int k = 0; k < 3; k++) {
  35. tmp[j][k] = dp[u][j][k];
  36. dp[u][j][k] = 0;
  37. }
  38. }
  39. for (int j = min(sz[u], x); j >= 0; j--) {
  40. for (int k = 0; k <= min(sz[e], j); k++) {
  41. dp[u][j][0] = (dp[u][j][0] + tmp[j - k][0] * (dp[e][k][0] + dp[e][k][1] + dp[e][k][2]) % mod) % mod;
  42. dp[u][j][1] = (dp[u][j][1] + tmp[j - k][1] * dp[e][k][0] % mod) % mod;
  43. dp[u][j][2] = (dp[u][j][2] + tmp[j - k][2] * (dp[e][k][0] + dp[e][k][2]) % mod) % mod;
  44. }
  45. }
  46. }
  47. }
  48. signed main() {
  49. // freopen("color.in", "r", stdin);
  50. // freopen("color.out", "w", stdout);
  51. cin >> n >> m;
  52. for (int i = 1; i <= n - 1; i++) {
  53. int u, v;
  54. cin >> u >> v;
  55. add_edge(u, v), add_edge(v, u);
  56. }
  57. cin >> k >> x;
  58. init(1, -1);
  59. dfs(1, -1);
  60. int res = 0;
  61. for (int i = 0; i <= x; i++) {
  62. for (int j = 0; j < 3; j++) res = (res + dp[1][i][j]) % mod;
  63. }
  64. cout << res << endl;
  65. }
添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注