树上游戏
给定一棵树，在上面等概率任意选取两条路径，记 $X$ 为两条路径的公共边数量，求 $X^2$ 的数学期望 $E(X^2)$ 模 $998244353$ 的值。
多测，$2 \leq n \leq 10^5$，$2 \leq \sum n \leq 10^6$。
数学、动态规划、树形动态规划
神秘拆式子，核心思维是分类讨论。
共有 $\left( \dfrac{n \times (n-1)}{2} \right)^2$ 种选择方案，算出所有选择方案中 $X^2$ 的总和再除以这个值即可。
考虑长度为 $k$ 的路径的贡献形式，其中 $e_i$ 为第 $i$ 条边的边权，本题中边权全部为 $1$，所以不容易想到拆分式子。
$$(e_1 + e_2 + \cdots + e_k)^2 = \sum_{i=1}^{k} |e_i|^2 + \sum_{1 \leq i,j \leq k, i \neq j} |e_i| \times |e_j|$$
贡献分为两种，第一种 $|e_i|^2$ 由公共边产生，第二种 $|e_i| \times |e_j|$ 和 $|e_j| \times |e_i|$ 由边有序对 $(e_i,e_j)$ 产生，由于 $|e_i|^2$ 的贡献只有一次，而第二种边的贡献有两次，二者需要分开计算。
指定一个根节点，然后在有根树上讨论，这里使用 $w_i$ 表示节点 $i$ 的子树大小。
边 $e_i$ 参与第一种贡献当且仅当两人选择的路径都包含边 $e_i$，设 $u$ 为边 $e_i$ 连接的儿子节点，那么两人选择的两组节点必定都满足一个在 $u$ 子树内，一个在 $u$ 子树外，一个人选择一个包含 $e_i$ 的路径的方案数为 $w_u (n - w_u)$，两个人都选中 $e_i$ 的方案数就为 $w_u^2 (n - w_u)^2$。
接下来计算边有序对 $(e_i,e_j)$ 的贡献，很显然这需要把 $e_i$ 和 $e_j$ 两条边连起来，设 $u$ 为 $e_i$ 连接的儿子节点，$v$ 为 $e_j$ 连接的儿子节点，分类讨论：
- 当 $u,v$ 为祖先后代关系时，考虑 $u$ 是 $v$ 的祖先的情况，贡献为 $w_v^2 (n-w_u)^2$。
- 当 $u,v$ 不为祖先后代关系时，贡献为 $w_u^2 w_v^2$。
在两条边路径上深度最大的点，即边对应点的 $\operatorname{lca}$ 处统计所有边节点对的贡献，维护子树大小平方和即可。
总体时间复杂度 $O(n)$。
#include<bits/stdc++.h>
using namespace std;
constexpr int mod=998'244'353;
int n,ans,w[100'005],s[100'005],sum[100'005];
vector<int> v[100'005];
inline int sq(int x){return 1ll*x*x%mod;}
int inv(int x){
int ret=1;
for(int i=mod-2;i;i>>=1){
if(i&1) ret=1ll*ret*x%mod;
x=1ll*x*x%mod;
}
return ret;
}
void dfs(int x,int las){
w[x]=1,sum[x]=0;
for(int i:v[x]) if(i!=las) dfs(i,x),w[x]+=w[i];
s[x]=sq(w[x]);
}
void dp(int x,int las){
for(int i:v[x]) if(i!=las){
dp(i,x);
ans=(ans+1ll*s[i]*sq(n-w[i])%mod)%mod;
ans=(ans+2ll*sq(n-w[i])*(sum[i]-s[i])%mod)%mod;
//注意这里 (sum[i]-s[i]) 是为了排除第一种贡献
ans=(ans+2ll*sum[x]*sum[i]%mod)%mod;
sum[x]=(sum[x]+sum[i])%mod;
}
sum[x]=(sum[x]+s[x])%mod;
}
void solution(){
cin>>n,ans=0;
for(int i=1;i<=n-1;i++){
static int x,y;
cin>>x>>y;
v[x].push_back(y);
v[y].push_back(x);
}
dfs(1,0),dp(1,0);
ans=1ll*ans*inv(sq(1ll*n*(n-1)%mod*inv(2)%mod))%mod;
ans=(ans+mod)%mod;
cout<<ans<<'\n';
for(int i=1;i<=n;i++) v[i].clear();
}
int T;
int main(){
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
cin>>T;
while(T--) solution();
return 0;
}