1003 - Counting Stickmen
给你一棵无根树,问你有多少个“火柴人”。(真的是火柴人)这题还挺有意思的
又是一个数数题。以下所有 $deg$ 为无向图度数,也就是有多少条边与其相连
可以发现对于每个火柴人,我们确定身体之后就可以进行计数。(图中 $3-5$ 这条边),记身体这条边靠头的点为 $x$,靠腿的点为 $y$。
我们在点 $y$ 处计算腿的方案数,在点 $x$ 处计算头和手的方案数。
腿较简单,考虑 $y$ 下方的 $k$ 条边即可 $k \choose 2$,等价于 $deg_y - 1\choose 2$。减去 $y - x$ 这条边。
头的方案数也较简单,是 $deg_x - 3$,减去两条手臂 + 一个身子。
考虑手臂的方案数,只需要考虑最外侧的点就可以确定一条手臂,形如图中 $6、10$ ,为 $\sum_\limits{u\in son(x)}(deg_u - 1)$。
但由于 $x$ 的子节点中有一个特殊的点 $y$,他下面的点是做腿的,所以还要再减掉 $deg_y - 1$。
到目前为止手臂的方案数为 $\sum_\limits{u\in son(x)}(deg_u - 1) - deg_y + 1\choose 2$
由于我们考虑最外侧的点,有一种情况是两个手从一个胳膊里伸出来。。。所以还要在减掉所有一个胳膊里两只手的情况,也就是 $\sum_\limits{u\in son(x), u\neq y} {deg_u - 1\choose 2}$。
综上,预处理出
$$
f(u) = deg_u - 1 , g(u) = {deg_u - 1\choose 2}
$$
$$
f_{sum} = \sum_\limits{u\in son(x)}f(u)
$$
$$
g_{sum} = \sum_\limits{u\in son(x), u\neq y} {g(u)}
$$
最后 dfs 把每部分乘起来即可。其中 $y$ 是 $u$ 的邻点。
$$
ans =\sum[(deg_u-3) * g(y) * \left[{f_{sum} - f(y)\choose 2} - (g_{sum} - g(y))\right]
$$
#pragma GCC optimize(3)
#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
...
Mint binom2(Mint x) {
return x * (x - 1) / 2;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int tt;
cin >> tt;
while (tt--) {
int n;
cin >> n;
vector<vector<int>> adj(n);
vector<int> deg(n);
for (int i = 1; i < n; i++) {
int u, v;
cin >> u >> v;
u--; v--;
adj[u].push_back(v);
adj[v].push_back(u);
deg[u]++;
deg[v]++;
}
vector<Mint> f(n), g(n); // sum of (deg[u] - 1) and sum of (deg[u] - 1 choose 2)
for (int i = 0; i < n; i++) {
f[i] = deg[i] - 1;
if (deg[i] - 1 >= 0) {
g[i] = binom2(deg[i] - 1);
}
}
Mint ans = 0;
function<void(int, int)> dfs = [&](int u, int pr) {
Mint f_sum = 0, g_sum = 0;
for (int v : adj[u]) {
f_sum += f[v];
g_sum += g[v];
if (v == pr) continue;
dfs(v, u);
}
for (int v : adj[u]) {
if (deg[u] - 3 >= 0) {
ans += (deg[u] - 3) * g[v] * (binom2(f_sum - f[v]) - (g_sum - g[v]));
}
}
};
dfs(0, -1);
cout << ans << '\n';
}
return 0;
}