你也许说得对，但我是真看不懂第一篇题解那个答案式子……
预处理是差不多的。
设 \(f_u\) 表示从 \(u\to fa(u)\) 的期望步数，\(g_u\) 为 \(fa(u)\to u\) 的期望步数，\(d_u\) 为 \(u\) 的度数。
那么显然有：
\[f_u=\frac{1}{d_u}\left(1+\sum\limits_{v\in son(u)}(1+f_v+f_u)\right) \]移项后得到 \(f_u=d_u+\sum\limits_{v\in son(u)}{f_v}\)。
求 \(g_u\) 的话要分两类：
- \(fa(u)\neq \text{root}\)：
- \(fa(u)=\text{root}\)：
由于 \(g_{\text{root}}=0\)，移项后均能得到 \(g_{u}=f_{fa(u)}+g_{fa(u)}-f_u\)。
然后就可以预处理出 \(f,g\) 了。
考虑所有路径 \(u\to v\)，统计从 \(u\) 走到 \(v\) 的期望步数，再除去 \(n^2\)。一条 \(u\to v\) 的路径，将其贡献与 \(v\to u\) 的路径合并。记一条边 \(e:(u, fa(u))\) 的权值为 \(w_e=f_u+g_u\)，\(\text{lca}(u,v)\) 为 \(k\)，就变成了经典问题。注意到：
\[\begin{aligned}&\sum\limits_{(u,v)}\left(\sum\limits_{p\in [u\to k]\setminus \{k\}}f_p+\sum\limits_{p\in [k\to v]\setminus \{k\}}g_p\right)\\=&\sum\limits_{u,v(\text{无序})}\left(\sum\limits_{p\in [u\to v]}(f_p+g_p)-f_k-g_k\right)\\=&\sum\limits_{e:(u, fa(u))}w_esz_u\left(n-sz_u\right)\end{aligned} \]第 \(2\) 步为考虑每条边对答案的贡献，即为穿过这条边的路径条数。
然后就很好做了。复杂度 \(O(n)\)。
#include <bits/stdc++.h>
#define int long long
using namespace std;
namespace vbzIO {
char ibuf[(1 << 20) + 1], *iS, *iT;
#if ONLINE_JUDGE
#define gh() (iS == iT ? iT = (iS = ibuf) + fread(ibuf, 1, (1 << 20) + 1, stdin), (iS == iT ? EOF : *iS++) : *iS++)
#else
#define gh() getchar()
#endif
#define rd read
#define wr write
#define pc putchar
#define pi pair<int, int>
#define mp make_pair
#define fi first
#define se second
#define pb push_back
#define ins insert
#define era erase
inline int read () {
char ch = gh();
int x = 0;
bool t = 0;
while (ch < '0' || ch > '9') t |= ch == '-', ch = gh();
while (ch >= '0' && ch <= '9') x = (x << 1) + (x << 3) + (ch ^ 48), ch = gh();
return t ? ~(x - 1) : x;
}
inline void write(int x) {
if (x < 0) {
x = ~(x - 1);
putchar('-');
}
if (x > 9)
write(x / 10);
putchar(x % 10 + '0');
}
}
using vbzIO::read;
using vbzIO::write;
const int N = 1e5 + 100;
const int mod = 998244353;
int n, ans, sz[N], f[N], g[N], d[N];
vector<int> t[N];
int qpow(int p, int q) {
int res = 1;
while (q) {
if (q & 1) res = 1ll * res * p % mod;
p = p * p % mod, q >>= 1;
}
return res;
}
void dfs1(int u, int fa) {
sz[u] = 1, f[u] = d[u];
for (int v : t[u]) {
if (v == fa) continue;
dfs1(v, u), f[u] += f[v], sz[u] += sz[v];
}
}
void dfs2(int u, int fa) {
if (u != 1) g[u] = f[fa] - f[u] + g[fa];
for (int v : t[u]) {
if (v == fa) continue;
dfs2(v, u);
}
if (u != 1) (ans += 1ll * (f[u] + g[u]) * sz[u] % mod * (n - sz[u]) % mod) %= mod;
}
signed main() {
n = rd();
for (int i = 1, u, v; i <= n - 1; i++) {
u = rd(), v = rd(), d[u]++, d[v]++;
t[u].pb(v), t[v].pb(u);
}
dfs1(1, 0);
dfs2(1, 0);
wr(1ll * ans * qpow(1ll * n * n % mod, mod - 2) % mod);
return 0;
}