Tree and Permutation
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 619 Accepted Submission(s): 214
Problem Description
There are N vertices connected by N−1 edges, each edge has its own length.
The set { 1,2,3,…,N } contains a total of N! unique permutations, let’s say the i-th permutation is Pi and Pi,j is its j-th number.
For the i-th permutation, it can be a traverse sequence of the tree with N vertices, which means we can go from the Pi,1-th vertex to the Pi,2-th vertex by the shortest path, then go to the Pi,3-th vertex ( also by the shortest path ) , and so on. Finally we’ll reach the Pi,N-th vertex, let’s define the total distance of this route as D(Pi) , so please calculate the sum of D(Pi) for all N!permutations.
The set { 1,2,3,…,N } contains a total of N! unique permutations, let’s say the i-th permutation is Pi and Pi,j is its j-th number.
For the i-th permutation, it can be a traverse sequence of the tree with N vertices, which means we can go from the Pi,1-th vertex to the Pi,2-th vertex by the shortest path, then go to the Pi,3-th vertex ( also by the shortest path ) , and so on. Finally we’ll reach the Pi,N-th vertex, let’s define the total distance of this route as D(Pi) , so please calculate the sum of D(Pi) for all N!permutations.
Input
There are 10 test cases at most.
The first line of each test case contains one integer N ( 1≤N≤105 ) .
For the next N−1 lines, each line contains three integer X, Y and L, which means there is an edge between X-th vertex and Y-th of length L ( 1≤X,Y≤N,1≤L≤109 ) .
The first line of each test case contains one integer N ( 1≤N≤105 ) .
For the next N−1 lines, each line contains three integer X, Y and L, which means there is an edge between X-th vertex and Y-th of length L ( 1≤X,Y≤N,1≤L≤109 ) .
Output
For each test case, print the answer module 109+7 in one line.
Sample Input
3
1 2 1
2 3 1
3
1 2 1
1 3 2
Sample Output
16
24
Source
大概题意：
给一棵N个节点的树， 求按N个节点全排列的顺序走一遍这棵树所得的路径贡献和。
解题思路：
对于所有按照全排列走过的路径，打表会发现，每两点之间的距离都出现了 (N-1)！次，所以我们只需要求出 所有两点之间的距离之和就可以解得最后的答案了。
也就是说我们只需要求出 ∑dis(i, j) 最后 ∑dis(i, j) * (N-1)! 就是答案了。
∑dis(i, j) 的求法：
我们可以根据当前节点 root 和 它的父节点 fa 的边 v 把一棵树分成两部分， 一部分是 以 fa 为根节点的子树，一部分是以 root 为根节点的子树（即除去这课子树是另一部分）。
如果我们已经预先知道了 fa 到 这棵树每个节点的距离和 sum_dis[ fa ], 以及以 root 为根节点的子树的大小t_size[ root ] ,那么 节点 root 到树上其他节点的距离和我们可以通过 sum_dis[ fa ]转化而来；
因为sum_dis[fa] 减去 v 对上面所分成的树的两部分的影响剩下的就是sum_dis[root] 即sum_dis[root] = sum_dis[fa] - (N-t_size[root])*v - t_size[root]*v ;
因此，我们第一步dfs把 1 到各个节点的距离和求出来，第二步通过对 1 的距离和转换 把其他节点的距离和求出来，最后所有距离和求和得出答案。
AC code：
1 #include <cstdio> 2 #include <iostream> 3 #include <cstring> 4 #include <cmath> 5 #define ll long long int 6 #define mod 1000000007 7 #define INF 0x3f3f3f3f 8 using namespace std; 9 10 const int MAXN = 1e5+10; 11 struct date{ 12 int v, next, len; 13 }node[MAXN<<1]; 14 ll sum_dis[MAXN]; 15 int t_size[MAXN]; 16 int head[MAXN], cnt; 17 int N; 18 19 void init() 20 { 21 memset(head, -1, sizeof(head)); 22 cnt = 0 ; 23 memset(sum_dis, 0, sizeof(sum_dis)); 24 memset(t_size, 0, sizeof(t_size)); 25 } 26 void add(int from, int to, int weight) 27 { 28 node[++cnt].next = head[from]; 29 head[from] = cnt; 30 node[cnt].v = to; 31 node[cnt].len = weight; 32 } 33 void dfs(int root, int fa, ll dis) 34 { 35 sum_dis[1] = (sum_dis[1]%mod+dis%mod)%mod; 36 t_size[root] = 1; 37 for(int x = head[root]; x != -1; x =node[x].next) 38 { 39 if(node[x].v != fa) 40 { 41 dfs(node[x].v, root, (dis+node[x].len)%mod); 42 t_size[root]+=t_size[node[x].v]; 43 } 44 } 45 } 46 void trans(int root, int fa) 47 { 48 int vv; 49 for(int i = head[root]; i != -1; i= node[i].next) 50 { 51 vv = node[i].v; 52 if(node[i].v != fa){ 53 sum_dis[vv] = (sum_dis[root]%mod+((1ll*(N-2*t_size[vv])*node[i].len)%mod)%mod)%mod; 54 if(sum_dis[vv] < 0) sum_dis[vv] += mod; 55 trans(vv, root); 56 } 57 } 58 } 59 int main() 60 { 61 int f, t, w; 62 while(~scanf("%d", &N)) 63 { 64 init(); 65 for(int i = 1; i < N; i++) 66 { 67 scanf("%d%d%d", &f, &t, &w); 68 add(f, t, w); 69 add(t, f, w); 70 } 71 dfs(1, 0, 0); 72 trans(1, 0); 73 ll P = 1, ans = 0; 74 for(int i = 1; i < N; i++) 75 P = 1ll*P*i%mod; 76 for(int i = 1; i <= N; i++) 77 ans = (ans + sum_dis[i])%mod; 78 ans = ans*P%mod; 79 printf("%lld ", ans); 80 } 81 return 0; 82 }