标签：return int sum Tree long v1 Game mod
- 应该坚持问题导向
- 你的思维疏漏之处在于，忽略了“乙烯型”的情况
- 本题其实并不是真正的数学期望型题目，因为可以通过除上\((\frac{n(n-1)}{2})^2\)将问题转化为统计所有公共路径长度的平方和
- 考虑拆贡献。设公共边为e1,e2,...,ek,\((|e1|+|e2|+...+|ek|)^2\)
- 分类讨论。|ei|产生的贡献：\([s[u]*(n-s[u])]^2\)
- |ei||ej|产生的贡献：
- 考虑在LCA处统计。考虑通过分类讨论增加条件
- 考虑按两条边是否位于LCA的同一子树分支分类讨论。为什么呢？因为这决定了是否可能自顶向下构造方案
- 如果是不同子树分支，那答案就是\((s[v1]*s[v2])^2\)，整合答案：sum[v1]*sum[v2]
- 如果是相同子树分支，则其中必定有一条边为(LCA,v1)，答案为\(((n-s[v1])*s[v2])^2\)，整合答案：\((n-s[v1])^2(sum[v1]-s[v1]^2)\)
- 注意别漏掉了完全平方公式的“2”了
点击查看代码
#include <bits/stdc++.h>
using namespace std;
vector<int>a[100005];
long long n,s[100005],sum[100005],ans;
const int mod=998244353;
int power(int n,int p)
{
if(p==0)
{
return 1;
}
long long tmp=power(n,p/2);
if(p%2==1)
{
return tmp*tmp%mod*n%mod;
}
return tmp*tmp%mod;
}
void dfs(int n1,int fa)
{
s[n1]=1;
sum[n1]=0;
for(int i=0;i<a[n1].size();i++)
{
if(a[n1][i]!=fa)
{
dfs(a[n1][i],n1);
s[n1]+=s[a[n1][i]];
ans=(ans+2*sum[a[n1][i]]*sum[n1]%mod)%mod;
(sum[n1]+=sum[a[n1][i]])%=mod;
ans=(ans+2*(n-s[a[n1][i]])*(n-s[a[n1][i]])%mod*(sum[a[n1][i]]-s[a[n1][i]]*s[a[n1][i]]%mod)%mod)%mod;
}
}
(sum[n1]+=(s[n1]*s[n1]%mod))%=mod;
if(fa)
{
ans=(ans+s[n1]*s[n1]%mod*(n-s[n1])%mod*(n-s[n1])%mod)%mod;
}
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
int T;
cin>>T;
while(T--)
{
long long cnt,cntinv;
cin>>n;
cnt=n*(n-1)/2%mod;
cntinv=power(cnt*cnt%mod,998244351);
for(int i=1;i<=n;i++)
{
a[i].clear();
}
for(int i=1;i<n;i++)
{
int u,v;
cin>>u>>v;
a[u].push_back(v);
a[v].push_back(u);
}
ans=0;
dfs(1,0);
cout<<(ans+mod)%mod*cntinv%mod<<endl;
}
return 0;
}
标签：return,
int,
sum,
Tree,
long,
v1,
Game,
mod
From： https://www.cnblogs.com/watersail/p/18520409