P3412\(\mathbf{} \begin{Bmatrix} \frac{{\Large LUOGU_P3412} }{{\color{Red}\Large Solution} }\mathbf{} {No.33} \end{Bmatrix}\times{}\) NeeDna
题意
给定一棵树，现在在树上随机游走，求从任意一点到任意一点的期望步数。
题解
这类树上游走的题有一个很经典的设计，我们先固定一个根 \(root\) 为终点，就是设 \(f_i\) 为自己到父亲的期望步数、设 \(d_i\) 为，此时\(f_{root}=0\)，对于叶子\(f_i=1\)。对于其他点，我们可以推出来这个 \(f_i\)。
我们发现这个 \(f_i\) 就是点 \(i\) 的子树的度数和，那么怎么用 \(f\) 来计算答案呢，我们发现固定 \(root\) 下每个点会经过的路径是确定的，所以对于每个点的期望就是从自己到 \(root\) 的所有点的期望和。反过来想，\(f_i\) 也就会被计算自己的子树大小（下文写作 \(sz_i\)）的次数，也就是说贡献是 \(f_i\times sz_i\)。这样我们暴力对每个点做 \(root\) 下计算就是 \(\Theta(n^2)\) 的。
怎么优化呢，我们发现其实很多时候 \(f_i\) 和 \(sz_i\) 都是一样的。所以我们分类讨论合并一下即可，先固定 \(root\) 设此时的 \(f\) 数组为 \(sumd\) 数组、\(sz\) 数组为 \(s\) 数组来防止混淆。对于所有可能的 \(root\) 每个点有如下几种情况：
-
该节点就是终点：\(f_i=0\)，\(sz_i=n\)，\(1\) 次。
-
终点在该节点的某一个儿子的子树 \(v\) 中：\(f_i=2\times n-2-sumd_v\)，\(sz_i=n-s_v\)，\(s_v\) 次。
-
终点不在该节点的某一个儿子的子树中：\(f_i=sumd_i\)，\(sz_i=s_i\)，\(n-s_i\) 次。
\(2\times n-2\) 是什么：是树上的度数和。
最后对于每一个节点直接统计即可，因为终点起点的匹配有 \(n^2\) 种，所以所有期望加起来要乘 \(n^2\) 的逆元。
code:
#include<bits/stdc++.h>
#define pb push_back
#define int long long
using namespace std;
const int N=1e5+10,mod=998244353;
int n,d[N],f[N],ans,sz[N],ft[N];
vector<int> g[N];
void dfs(int u,int fa){sz[u]=1;f[u]=d[u];ft[u]=fa;for(int v:g[u]){if(v==fa) continue;dfs(v,u);int x=2*n-2-f[v];ans=(ans+((n-sz[v])*sz[v]%mod)*x)%mod;sz[u]+=sz[v];f[u]+=f[v];}ans=(ans+((sz[u]*(n-sz[u]))%mod)*f[u])%mod;
}
int ksm(int x,int k){int ans=1;while(k){if(k%2) ans=ans*x%mod;x=x*x%mod;k/=2;}return ans;
}
signed main(){cin>>n;for(int i=1,u,v;i<n;i++){cin>>u>>v;d[u]++,d[v]++;g[u].pb(v);g[v].pb(u);}dfs(1,0);cout<<ans*ksm(n*n%mod,mod-2)%mod;return 0;
}