本文共 2125 字，大约阅读时间需要 7 分钟。
传送门
经过组合数学推导可得 题目要求2*(n-1)!*树上路径总和
路径总和可以通过边dfs边计算
每一条边的贡献为 siz*(n-siz)次 siz为子树大小
/** Copyright(c) All rights reserved. Author : @klay Date : 2018-08-28-20.16.35 Description : 树上任意两点路径总和*/#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #define A first#define B second#define mp make_pair#define pb push_back#define pw(x) (1ll << (x))#define sz(x) ((int)(x).size())#define all(x) (x).begin(),(x).end()#define rep(i,l,r) for(int i=(l);i<(r);i++)#define per(i,r,l) for(int i=(r);i>=(l);i--)#define FOR(i,l,r) for(int i=(l);i<=(r);i++)#define eps 1e-9#define PIE acos(-1)#define cl(a,b) memset(a,b,sizeof(a))#define fastio ios::sync_with_stdio(false);cin.tie(0);#define lson l , mid , ls#define rson mid + 1 , r , rs#define ls (rt<1)#define rs (ls|1)#define INF 0x3f3f3f3f#define lowbit(x) (x&(-x))#define sqr(a) a*a#define ll long long#define vi vector #define pii pair #define dd(x) cout << #x << " = " << (x) << ", "#define de(x) cout << #x << " = " << (x) << "\n"#define endl "\n"using namespace std;//**********************************const int maxn=1e5+7;const int mod=1e9+7;struct Edge{ int to,dist,next;}edge[maxn];int tot,n,m,head[maxn],fac[maxn+7]={ 1};ll ans;//**********************************void Init(){ tot=0; ans=0; cl(head,-1);}void getfac(){ FOR(i,1,maxn)fac[i]=fac[i-1]*i%mod;}void add_edge(int from,int to,int dist){ edge[tot].to=to; edge[tot].dist=dist; edge[tot].next=head[from]; head[from]=tot++;}int dfs(int u,int fa){ int size=1; for(int i=head[u];~i;i=edge[i].next){ int v=edge[i].to; int siz=dfs(v,u); ll tmp=siz%mod*(n-siz)%mod*2%mod*(fac[n-1])%mod*edge[i].dist%mod; ans=(ans+tmp)%mod; size+=siz; } return size;}//**********************************int main(){ getfac(); while(~scanf("%d",&n)){ Init(); int u,v,w; rep(i,0,n-1)scanf("%d%d%d",&u,&v,&w),add_edge(u,v,w),add_edge(v,u,w); dfs(1,-1); printf("%lld\n",ans); } return 0;}
转载于:https://www.cnblogs.com/klaycf/p/9550841.html