【2018 CCPC网络赛】1009

题目地址：http://acm.hdu.edu.cn/showproblem.php?pid=6446

题目给出的数据为一棵树，dfs扫描每条边，假设去掉某条边，则左边 x 个点，右边 n-x 个点，则经过该条边共有 x*(n-x) 种组合，又因为 1~n 全排列有 n! 种，故 a~b，包含 b~a 这条边的贡献为 (n-x)*x*2*(n-1)!*w;

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<vector>
 4 using namespace std;
 5 
 6 #define LL long long
 7 const int MOD = 1e9+7;
 8 const int N = 1e5+5;
 9 struct EDGE {
10     LL to, length;
11 };
12 vector<EDGE> edge[N];
13 LL n, factorial[N], lchild[N], w[N];
14 
15 int dfs(int k, int pre) {
16     int size = edge[k].size(), ans=1;
17     for(int i=0; i<size; i++) {
18         if(edge[k][i].to == pre)
19             w[k] = edge[k][i].length;
20         else
21             ans += dfs(edge[k][i].to, k);
22     }
23     return lchild[k] = ans;
24 }
25 
26 int main()
27 {
28     factorial[1] = 1;
29     for(int i=2; i<N; i++)
30         factorial[i] = factorial[i-1]*i%MOD;
31     
32     while(~scanf("%d",&n))
33     {
34         LL  ans=0;
35         for(int i=1; i<=n; i++) {
36             edge[i].clear();
37         }
38         for(int x,y,v,i=1; i<n; i++) {
39             scanf("%d%d%d", &x, &y, &v);
40             edge[x].push_back({y,v});
41             edge[y].push_back({x,v});
42         }
43         
44         dfs(1, -1);
45         for(int i=2; i<=n; i++) {
46             LL tmp=1;
47             tmp = lchild[i]*(n-lchild[i])%MOD;
48             tmp = 2*factorial[n-1]%MOD*w[i]%MOD*tmp%MOD;
49             ans = (ans+tmp)%MOD;
50         }
51         cout<<ans<<endl;
52     }
53     return 0;
54 }