LuoTianyi and the Floating Islands (Hard Version)

LuoTianyi and the Floating Islands (Hard Version)

Problem

有⼀棵 \(n\) 个节点的树，随机选择 \(k\) 个不同节点作为“有⼈的岛屿”，定义⼀个节点是“好岛”，如果它到所有 \(k\) 个有⼈岛屿的距离之和，在所有节点中最⼩。 求“好岛”数量的期望值，对 \(10^9+7\) 取模。

Solution

因为要使离其他几个点的距离最小

在草稿纸上画几个图就会发现

如果 \(k\) 是奇数，那么在图上就只存在一个点满足条件

所以输出1

• 理解

  因为当一个点是最优点时，一定有某种方法将这个点的子树分成两个部分

  使得两个部分中的有⼈的岛屿个数相同

  而因为是奇数，所以最优点一定在有⼈的岛屿上

如果 \(k\) 是偶数

这里一个错误的思路就是考虑答案整条链（比如我想了好久才跳出来）

但是我们可以对于边进行考虑

枚举每一条边

对于上半部分和下半部分，此时上下的有⼈的岛屿的数量均为 \(k/2\)

直接枚举组合数

\[\binom{siz_u}{\frac{k}{2}} \times \binom{n - siz_u}{\frac{k}{2}}\]

对于边的期望进行累加

众所周知

点的期望 = 边的期望 + 1

Code

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 2e5 + 10, p = 1e9 + 7;
int n, k, fac[N], inv[N], siz[N];
vector <int> e[N];
int qpow(int a, int b) {int res = 1, mul = a;while (b) {if (b & 1) res = res * mul % p;mul = mul * mul % p, b >>= 1;}return res;
}
void pre(int maxn) {fac[0] = inv[0] = 1;for (int i = 1; i <= maxn; i++) fac[i] = fac[i - 1] * i % p;inv[maxn] = qpow(fac[maxn], p - 2);for (int i = maxn - 1; i >= 1; i--) inv[i] = inv[i + 1] * (i + 1) % p;
}
int C(int n, int m) {if (n < 0 || m < 0 || m > n) return 0;return fac[n] * inv[m] % p * inv[n - m] % p;
}
int ans = 0;
void dfs(int u, int fa) {siz[u] = 1;for (auto v : e[u]) {if (v == fa) continue;dfs(v, u);siz[u] += siz[v];}ans += C(siz[u], k / 2) * C(n - siz[u], k / 2) % p;ans %= p;
}
signed main() {cin >> n >> k;pre(n);if (k & 1) {cout << 1; return 0;}for (int u, v, i = 1; i < n; i++) cin >> u >> v, e[u].emplace_back(v), e[v].emplace_back(u);dfs(1, 0);cout << (1 + ans * qpow(C(n, k), p - 2)) % p;return 0;
}