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.

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 ) .

Output

For each test case, print the answer module 109+7 in one line.

Sample Input

1 2 1

2 3 1

1 2 1

1 3 2

Sample Output

Source

2018中国大学生程序设计竞赛 - 网络选拔赛

大概题意：

给一棵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：

 #include <cstdio>

 #include <iostream>

 #include <cstring>

 #include <cmath>

 #define ll long long int

 #define mod 1000000007

 #define INF 0x3f3f3f3f

 using namespace std;

 const int MAXN = 1e5+;

 struct date{

     int v, next, len;

 }node[MAXN<<];

 ll sum_dis[MAXN];

 int t_size[MAXN];

 int head[MAXN], cnt;

 int N;

 void init()

 {

     memset(head, -, sizeof(head));

     cnt =  ;

     memset(sum_dis, , sizeof(sum_dis));

     memset(t_size, , sizeof(t_size));

 }

 void add(int from, int to, int weight)

 {

      node[++cnt].next = head[from];

      head[from] = cnt;

      node[cnt].v = to;

      node[cnt].len = weight;

 }

 void dfs(int root, int fa, ll dis)

 {

     sum_dis[] = (sum_dis[]%mod+dis%mod)%mod;

     t_size[root] = ;

     for(int x = head[root]; x != -; x =node[x].next)

     {

         if(node[x].v != fa)

         {

             dfs(node[x].v, root, (dis+node[x].len)%mod);

             t_size[root]+=t_size[node[x].v];

         }

     }

 }

 void trans(int root, int fa)

 {

     int vv;

     for(int i = head[root]; i != -; i= node[i].next)

     {

         vv = node[i].v;

         if(node[i].v != fa){

             sum_dis[vv] = (sum_dis[root]%mod+((1ll*(N-*t_size[vv])*node[i].len)%mod)%mod)%mod;

             if(sum_dis[vv] < ) sum_dis[vv] += mod;

             trans(vv, root);

         }

     }

 }

 int main()

 {

     int f, t, w;

     while(~scanf("%d", &N))

     {

         init();

         for(int i = ; i < N; i++)

         {

             scanf("%d%d%d", &f, &t, &w);

             add(f, t, w);

             add(t, f, w);

         }

         dfs(, , );

         trans(, );

         ll P = , ans = ;

         for(int i = ; i < N; i++)

             P = 1ll*P*i%mod;

         for(int i = ; i <= N; i++)

             ans = (ans + sum_dis[i])%mod;

         ans = ans*P%mod;

         printf("%lld\n", ans);

     }

     return ;

 }

巴特西

2018中国大学生程序设计竞赛 - 网络选拔赛 1009 - Tree and Permutation 【dfs+树上两点距离和】