难度：。
比较无聊的题。先考虑一个比较暴力的做法。枚举根 ，然后再枚举点集 的 LCA 所在位置 。可以一遍 dfs 求出 数组表示 点为根的子树，然后直接组合数统计答案。具体的，固定 后的答案为：
但是这样做时间复杂度过于爆炸，考虑逐步优化。枚举 后内层还有一个对所有子节点的求和，考虑将其拆出，即直接一次性单独统计完每个点对答案的贡献。那么可以发现 点的贡献可以分成两个部分：
- 自己直接贡献的部分 。
- 被父亲结点减去贡献的部分 ，其中 表示 点的父亲结点。
所以答案也可以被表示为（固定 ）：
直接枚举 可以做到总时间复杂度 求解，但是这样显然是不行的。容易想到换根 dp 来维护这个东西。先 计算出 时的答案 ，然后套路的从 结点开始 DFS 遍历整棵树，假设当前求出了 的值，然后现在枚举 的儿子结点 要求 的值，计算其相对于 的变化量。发现上面那个公式用到的量里面显然只有 数组发生了变化。而考虑经典结论，根结点从 变为 只会修改 两个位置的值，因此直接对这两个位置分别讨论计算变化的量即可。
预处理阶乘和阶乘逆可以做到 解决整个问题。
namespace Loyalty
{
vector<int> adj[N];
int fac[N], inv[N], ifac[N], n, k;
inline void init()
{
for (int i = 0; i < 2; ++i)
fac[i] = inv[i] = ifac[i] = 1;
for (int i = 2; i < N; ++i)
{
fac[i] = fac[i - 1] * i % mod;
inv[i] = mod - inv[mod % i] * (mod / i) % mod;
ifac[i] = ifac[i - 1] * inv[i] % mod;
}
}
inline int binom(int a, int b)
{
if (b < 0 || a < b)
return 0;
return fac[a] * ifac[b] % mod * ifac[a - b] % mod;
}
int presolve[N], siz[N], res[N], up[N];
inline void dfs(int u, int fa)
{
siz[u] = 1, up[u] = fa;
for (int &v : adj[u])
if (v != fa)
dfs(v, u), siz[u] += siz[v];
}
inline void dfs2(int u, int fa)
{
if (u != 1)
{
int term1 = ((n - siz[u]) % mod) * binom(siz[u], k) % mod; // (n-sz)*C(sz,k)
int term2 = (siz[u] % mod) * binom(n - siz[u], k) % mod; // sz*C(n-sz,k)
int term3 = ((presolve[fa] - binom(siz[u], k) + mod) % mod) * (siz[u] % mod) % mod; // (S_fa - C(sz))*sz
int term4 = ((presolve[u] - binom(n - siz[u], k) + mod) % mod) * ((n - siz[u]) % mod) % mod; // (S_u - C(n-sz))*(n-sz)
res[u] = (res[fa] + term1 - term2 + term3 - term4) % mod;
if (res[u] < 0)
res[u] += mod;
}
for (int &v : adj[u])
if (v != fa)
dfs2(v, u);
}
inline void main([[maybe_unused]] int _ca, [[maybe_unused]] int _atc)
{
cin >> n >> k;
for_each(adj + 1, adj + n + 1, [&](auto &edges) { edges.clear(); });
for (int i = 1; i < n; ++i)
{
int a, b;
cin >> a >> b;
adj[a].emplace_back(b);
adj[b].emplace_back(a);
}
dfs(1, 0);
for (int i = 1; i <= n; ++i)
res[1] = (res[1] + (siz[i] - siz[up[i]]) * binom(siz[i], k) % mod) % mod;
for (int i = 1; i <= n; ++i)
{
presolve[i] = binom(n - siz[i], k);
for (int &j : adj[i])
if (j != up[i])
presolve[i] = (presolve[i] + binom(siz[j], k)) % mod;
}
dfs2(1, 0);
cout << (accumulate(res + 1, res + n + 1, 0ll) % mod + mod) % mod << '\n';
}
}
喜欢的话，留下你的评论吧～