P3412 仓鼠找sugar II 题解
大水题一个
题目大意
给定你一个树，设 \(f_{u, v}\) 表示在树上随机游走的情况下从 \(u\) 走到 \(v\) 的期望步数，求 \(\displaystyle \frac{\sum_{i = 1}^n \sum_{j = 1}^n f_{i, j}}{n^2}\)。
题解
不难想到 dp，不过 \(1e5\) 的范围差点让我怀疑我 \(O(n)\) 的 dp。先设一下状态，设 \(f_u\) 表示 \(u\) 子树内的所有点全都走到点 \(u\) 的期望步数。答案就是以每个点为根时根的 \(f\) 值的和。
考虑怎么转移。
似乎不好直接转，于是想想我们转移时什么东西卡住了我们。假设现在 \(u\) 子树内的所有点都走到了 \(u\)，那么我们现在想要让这些点再从 \(u\) 结点走向它的父亲结点，这个期望步数不好直接求。
于是我们再设 \(g_u\) 表示从 \(u\) 结点走到它的父亲结点的期望步数。先来考虑它的转移。\(deg_u\) 表示 \(u\) 结点的度，即与它相连的边数，\(son_u\) 表示 \(u\) 结点的儿子构成的集合。
\[\begin{aligned} g_u &= \frac{1}{deg_u} + \sum_{v \in son_u} \frac{1 + g_v + g_u}{deg_u}\\ deg_u \times g_u &= 1 + \sum_{v \in son_u} (1 + g_v + g_u)\\ &= 1 + (deg_u - 1) + (deg_u - 1) \times g_u + \sum_{v \in son_u} g_v\\ &= deg_u + (deg_u - 1) \times g_u + \sum_{v \in son_u} g_v\\ g_u &= deg_u + \sum_{v \in son_u} g_v \end{aligned}\]\(g\) 的转移就没了，再来考虑 \(f\)。
\[\begin{aligned} f_u &= \sum_{v \in son_u} f_v + size_v \times g_v \end{aligned}\]这个非常好理解。
于是可以打 \(n^2\) 了。
换一下根，就 \(O(n)\) 了。
设 \(h(x)\) 为以 \(x\) 为根时 \(x\) 的 \(f\) 值，那么有：
\[\begin{aligned} h_u &= f_u + (h_{fa} - f_u - size_u \times g_u) + (n - size_u) \times (g_{fa} - g_u) \end{aligned}\]最终答案为 \(\displaystyle \frac{\sum_i^n h_i}{n^2}\)。
然后就没了。
代码
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int M = 100005;
const int mod = 998244353;
int n, f[M], g[M], siz[M], out[M], inv, ans, h[M];
int from[M << 1], to[M << 1], head[M], nex[M << 1], tot;
inline void add_edge(int u, int v) {
from[++ tot] = u;
to[tot] = v;
nex[tot] = head[u];
head[u] = tot;
}
void dfs1(int u, int fa) {
g[u] = out[u];
siz[u] = 1;
for(int i = head[u]; i; i = nex[i]) {
int v = to[i];
if(v == fa)
continue;
dfs1(v, u);
siz[u] += siz[v];
g[u] = (g[u] + g[v]) % mod;
f[u] = (f[u] + f[v] + siz[v] * g[v] % mod) % mod;
}
}
void dfs2(int u, int fa) {
h[u] = (f[u] + (h[fa] - f[u] + mod - siz[u] * g[u] % mod + mod) % mod + (n - siz[u]) * ((g[fa] - g[u] + mod) % mod) % mod) % mod;
g[u] = g[u] + (g[fa] - g[u]);
ans = (ans + h[u]) % mod;
for(int i = head[u]; i; i = nex[i]) {
int v = to[i];
if(v == fa)
continue;
dfs2(to[i], u);
}
}
inline int quick_pow(int base, int ci, int pp) {
int res = 1;
while(ci) {
if(ci & 1)
res = res * base % pp;
base = base * base % pp;
ci >>= 1;
}
return res;
}
signed main() {
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
cin >> n;
inv = quick_pow(n, mod - 2, mod);
for(int i = 1; i < n; ++ i) {
int u, v;
cin >> u >> v;
add_edge(u, v);
add_edge(v, u);
++ out[u];
++ out[v];
}
dfs1(1, 0);
ans = f[1];
h[1] = f[1];
for(int i = head[1]; i; i = nex[i])
dfs2(to[i], 1);
ans = ans * inv % mod * inv % mod;
cout << ans;
}