彼方へ、名もなき海辺より

Mier_Samuelle · 2026-07-19 23:14:36 · 题解

:::info[记号]{open}

:::

手玩几个样例可发现，连通块的个数就是环的个数。考虑什么时候会形成环，要是 \text{path}(u,v) 上的所有除 v 以外的节点都指向路径上的下一个节点，而 v 指向了 u，就会形成环。参见下图：

:::align{center}

如图，\text{path}(2,5) 上除 5 以外的节点都指向路径上的下一个节点，而 5 指向了 2，因此形成了环。

:::

考虑在 v 处计算贡献，先钦定 \text{path}(u,v) 上的节点形成环，然后让剩下的节点随便乱连。设节点 u 有 d_u 个可以连的节点，记 W=\prod_{i=1}^n w_i，则答案为

整理得

暴力是 O(n^3) 的，考虑优化。记

若 x 是 u 的一个子节点，那么有

这样便可用一次遍历求出所有 f_u 了。复杂度 O(n \log p)，O(\log p) 为求逆元的复杂度。

:::success[Code]{open}

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int MAXN = 5e5 + 10;
const int MOD = 998244353;
vector <int> adj[MAXN];
int deg[MAXN], dep[MAXN], inv[MAXN], w[MAXN], f[MAXN], n;
int qpow(int x, int y){
    int res = 1;
    while (y){
        if (y & 1){
            res = res * x % MOD;
        }
        x = x * x % MOD;
        y >>= 1;
    }
    return res;
}
void dfs(int u, int fa){
    dep[u] = dep[fa] + 1;
    if (dep[u] == 1){
        w[u] = dep[u] + deg[u] - 1;
    }
    else{
        w[u] = dep[u] + deg[u] - 2;
    }
    inv[u] = qpow(w[u], MOD - 2);
    f[u] = (f[fa] * inv[u] % MOD + inv[u] * inv[fa] % MOD) % MOD;
    for (int v : adj[u]){
        if (v == fa){
            continue;
        }
        dfs(v, u);
    }
    return;
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> n;
    for (int i = 1; i < n; i++){
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
        deg[u]++;
        deg[v]++;
    }
    dfs(1, 0);
    int mul = 1, sum = 0;
    for (int i = 1; i <= n; i++){
        mul = mul * w[i] % MOD;
        sum = (sum + f[i]) % MOD;
    }
    cout << mul * sum % MOD << "\n";
    return 0;
}

:::