2018中国大学生程序设计竞赛 - 网络选拔赛 1009 Tree and Permutation & HDU 6446_there are $n$ vertices connected by $n-1$ edges, e

Tree and Permutation
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 46 Accepted Submission(s): 16

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
3
1 2 1
2 3 1
3
1 2 1
1 3 2

Sample Output
16
24

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

Recommend

Tree and Permutation
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 46 Accepted Submission(s): 16

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
3
1 2 1
2 3 1
3
1 2 1
1 3 2

Sample Output
16
24

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

Recommend

新鲜出炉的热乎题啊。题意是对于一个全排列，求出1到N的花费和。求出这个N个数的全排列的所有和。很容易发现规律
比如3的全排列有 {1,2,3},{1,3,2},{2,3,1},{2,1,3},{3,2,1},{3,1,2}。这里面有C(n,2)条不同的边，即1-2,1-3,2-3,这三条边，每个次数都是相同的为总边数N!(N-1)除以边数C(n,2)，化简后为(N-1)! 2,所以我们只有求出任意两个边的总权值之和再乘以每个边次数，就能得到结果了。
因为这里给的顺序是按照图给的，所以我们用BFS把它分层，当作树来存储。对于这一棵树，先不考虑边的权值，对于每条边，可以把整棵数分为两个点集。两个点集个数相乘之后的结果就是这个边被计算的次数。最后在再乘以这个边的权值即可。
可以考虑看下这道题目的题解https://nanti.jisuanke.com/t/16446

代码如下：

#include<bits/stdc++.h>

using namespace std;
const int MAX = 1e5+10;
typedef long long ll;
const ll Mod = 1e9+7;
class Edge{
public:
    int to,cost;
    Edge();
    Edge(int _to,int _cost);
};
vector<Edge> CG[MAX];
vector<int> G[MAX];
int N;
ll num[MAX],sum[MAX],len[MAX];
void add_Edge(int u,int v,int w){
    CG[u].push_back(Edge(v,w));
    CG[v].push_back(Edge(u,w));
}
bool used[MAX];
//把这棵树重建
void ReBuild(){
    memset(used,false,sizeof(used));
    queue<int> que;
    que.push(1);
    used[1] = true;
    while(!que.empty()){
        int v = que.front();que.pop();
        for(int i=0;i<CG[v].size();++i){
            Edge &e = CG[v][i];
            if(!used[e.to]){
                que.push(e.to);
                G[v].push_back(e.to);
                len[e.to] = e.cost;
                used[e.to] = true;
            }
        }
    }
}
//获得每个边左边节点个数。节点相当于代表这个边的左边个数。
ll dfs(int now){
    ll tot = 1;
    for(int i=0;i<G[now].size();++i){
        tot += dfs(G[now][i]);
    }
    num[now] = tot;
    return tot;
}
void cal_sum()
{
    for(int i=1;i<=N;i++)
    {
        sum[i]=num[i]*(N-num[i])%Mod;
    }
}
ll Fac[MAX];
void init(){
    Fac[0] = 1;
    Fac[1] = 1;
    for(int i=2;i<=1e5;++i)
        Fac[i] = Fac[i-1]*i%Mod;
}
int main(void){
    init();
    //freopen("3.in","r",stdin);
    while(scanf("%d",&N) != EOF){
        for(int i=1;i<=N;++i){
            CG[i].clear();
            G[i].clear();
        }
        int u,v,w;
        for(int i=1;i<N;++i){
            scanf("%d%d%d",&u,&v,&w);
            add_Edge(u,v,w);
        }
        ReBuild();
        dfs(1);
        cal_sum();
        ll res = 0;
        for(int i=1;i<=N;++i){
            res = (res + sum[i]%Mod*len[i]%Mod)%Mod;
        }
        ll ss = Fac[N-1]*2%Mod*res%Mod;
        printf("%lld\n",ss);
    }
    return 0;
}

Edge::Edge(){
    to = cost = 0;
}
Edge::Edge(int _to,int _cost){
    to = _to;
    cost = _cost;
}
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
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97