没啥好说的,拆一下贡献就完事了.记dis(x,y)为树上x到y的最短路径,设长度为n的排列中有f(n)个里面x和y相邻(不考虑x和y的顺序),那么f(n)=(n-2)! (n-1) 2,显然这个f(n)和x,y具体是谁没啥关系.那么就把树上任意两点之间的路径长度再求个和乘上f(n)就行了.树上任意两点之间的路径长度之和也可以拆贡献,分别考虑每一条边,看这条边两侧分别有a,b个点那么就有2ab个有序点对满足之间的路径经过这条边.少取模WA了一次. ~咸鱼选手又有了能翻身的错觉~
#include<cstdio> const int mod=(int)(1e9+7); const int maxn=100005; struct edge{ int to,next,w; }lst[maxn<<1];int cnt=0; int first[maxn]; void addedge(int a,int b,int w){ lst[++cnt].next=first[a]; lst[cnt].to=b;lst[cnt].w=w; first[a]=cnt; } int fac[maxn]; int sz[maxn]; int n; int ans=0; void dfs(int x,int prt){ sz[x]=1; for(int pt=first[x];pt;pt=lst[pt].next){ if(lst[pt].to==prt)continue; dfs(lst[pt].to,x);sz[x]+=sz[lst[pt].to]; ans+=sz[lst[pt].to]*2ll*(n-sz[lst[pt].to])%mod*lst[pt].w%mod;ans%=mod; } } int qpow(int a,int x){ int ans=1; for(;x;x>>=1,a=a*1ll*a%mod){ if(x&1)ans=ans*1ll*a%mod; } return ans; } int ifac[maxn]; int C(int n,int m){ return fac[n]*1ll*ifac[m]%mod*ifac[n-m]%mod; } int main(){ fac[0]=1; for(int i=1;i<maxn;++i)fac[i]=i*1ll*fac[i-1]%mod; ifac[maxn-1]=qpow(fac[maxn-1],mod-2); for(int i=maxn-1;i>=1;--i)ifac[i-1]=ifac[i]*1ll*i%mod; while(scanf("%d",&n)!=EOF){ ans=0;cnt=0;for(int i=1;i<=n;++i)first[i]=0; for(int i=1,u,v,w;i<n;++i){ scanf("%d%d%d",&u,&v,&w); addedge(u,v,w);addedge(v,u,w); } dfs(1,-1); int g=0; for(int i=0;i<=n-2;++i){ g+=fac[i]*1ll*fac[n-2-i]%mod*C(n-2,i)%mod;g%=mod; } printf("%d\n",g*1ll*ans%mod); } return 0; }转载于:https://www.cnblogs.com/liu-runda/p/9877697.html
相关资源：数据结构—成绩单生成器