1009 Tree and Permutation
题目
Problem
There are vertices connected by edges, each edge has its own length.
The set { } contains a total of unique permutations, let’s say the
-th permutation is and is its -th number.
For the -th permutation, it can be a traverse sequence of the tree with vertices,
which means we can go from the -th vertex to the -th vertex by the shortest
path, then go to the -th vertex ( also by the shortest path ) , and so on. Finally
we’ll reach the -th vertex, let’s define the total distance of this route as ,
so please calculate the sum of for all permutations.
Input
There are 10 test cases at most.
The first line of each test case contains one integer ( ) .
For the next lines, each line contains three integer , and , which means
there is an edge between -th vertex and -th of length (
) .
Output
For each test case, print the answer module in one line.
Sample Input
3
1 2 1
2 3 1
3
1 2 1
1 3 2
Sample Output
16
24
题意
给出n个点(1,2,3…..n)，用n-1条边连接，从第i点到第j点的路径取它们之间的最短路径，在某种排列下，从第一个节点到最后一个节点的距离为该排列的距离，求全排列的总距离和。
题解
1、写几个全排列可以发现：在n个节点的全排列中，每一条路径被计算了 (n-1)*2 次。
2、用dp求出每两节点的距离和，而每两节点的距离之和就是所有路径之和。求在总路径和里每条边被计算了几次——>son[a] * (n-son[a])次。
1 |
|
