Fork me on GitHub

2018网络赛（一）1009 Tree and Permutation

发表于 | 分类于

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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#define ll long long
using namespace std;
typedef pair<int,ll>edge;
const int maxn = 1e5+1;
const ll mod = 1e9+7;
vector<edge>emm[maxn];
ll dp[maxn];//当前节点和她所有下层节点的路径和
ll fac[maxn];//记录阶乘
int son[maxn],n;//去掉一条边后，分成两份节点，son指其中一份
inline void init()//计算(n-1)!
{
    fac[0] = 1;
    for(int i=1; i<maxn; i++) fac[i] = fac[i-1] * i % mod;
}
void dfs(int rt,int fa)//rt是当前结点，fa是上一个结点
{
    son[rt] = 1;//初始化当前结点
    for(auto v:emm[rt])//遍历容器中的每个值——>遍历每个和当前结点相连的结点
    {
        int to = v.first;//当前结点连通的结点
        ll val = v.second;//当前结点到连通结点的边的权值
        if(to == fa)//如果当前结点连接的是上一个结点，就不再计算该节点——>去重
            continue;
        dfs(to,rt);
        son[rt] += son[to];//求结点连通的结点和
        ll tmp = 1LL * son[to] * (n - son[to]) % mod;//当前边被计算了几次
        dp[rt] = (dp[rt] + (dp[to] + tmp * val % mod) % mod) % mod;//当前结点(包括它的子节点)贡献的路程
    }
}
int main()
{
    init();
    while(~scanf("%d",&n))  //输入结点数
    {
        memset(dp,0,sizeof(dp));//初始化
        memset(son,0,sizeof(son));
        for(int i=0; i<maxn; i++)
            emm[i].clear();
        int u,v;//u起点,v终点
        ll val;
        for(int i=1; i<n; i++)//记录给出路径
        {
            scanf("%d%d%lld",&u,&v,&val);
            emm[u].push_back(make_pair(v,val));
            emm[v].push_back(make_pair(u,val));
        }
        dfs(1,0);
        printf("%lld\n",dp[1]*fac[n-1]%mod*2%mod);
    }
    return 0;
}