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

Tree and Permutation

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)Total Submission(s): 0 Accepted Submission(s): 0

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

题意:

首先给出一个含有n个节点的树,边权为距离。

对于1-n的某一种排列p1,p2,p3……pn,贡献为dis(p1,p2)+dis(p2,p3)+dis(p3,p4)+……+dis(pn-1,pn)

求所有排列的贡献和

题解:

一棵树n个结点n-1条边,所以任意两点之间都有最短距离。由于所有遍历方式可以看做n个结点的排列,而每次有直接关系的只有两点之间的距离,因此只需求出两点之间的距离在所有排列中一共出现多少次即可。

比如n=2时,两个点1,2,共有两种排列方式,即1,2,和2,1

n=3时,三个点1,2,3,其中1,2共有4种方法得到,即1,2,3,和2,1,3,和3,1,2,和3,2,1

n=4时,三个点1,2,3,4,其中1,2共有12种方法得到,即1,2,3,4,和1,2,4,3,和2,1,3,4,和2,1,4,3,和3,1,2,4,和3,2,1,4和4,1,2,3,和4,2,1,3,和3,4,1,2,和4,3,1,2,和3,4,2,1,和4,3,2,1,

n=jie[n-1]*(n-1)。

先用树状dp求出所有两两结点之间的距离之和,再乘以每条边在所有结点排列的n!方式中一共用到的次数。

代码:

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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e5+7;
const ll mod = 1e9+7;
ll sum[maxn], n;
ll dp[maxn];
ll jie[maxn];
ll jie2[maxn];
struct Edge
{
ll v, w;
};
vector<Edge> tree[maxn];
void init(){
jie[2] = 2;
for(ll i = 3;i<maxn;i++){
jie[i] = jie[i-1]*(i-1)%mod;
}
}
void dfs(ll cur, ll father)
{
sum[cur] = 1;
for(ll i = 0; i < tree[cur].size(); i++)
{
ll son = tree[cur][i].v;
ll len = tree[cur][i].w;
if(father == son)
continue;
dfs(son, cur);
sum[cur] += sum[son]%mod;
sum[cur]%=mod;
dp[cur] += (dp[son]%mod + (n-sum[son])%mod*sum[son]%mod * len%mod)%mod;
dp[cur]%=mod;
}
}
int main()
{
init();
ll u, v, w;
while(scanf("%lld", &n)!=EOF)
{
if(n<=2){
if(n==1){
printf("0\n");
continue;
}
scanf("%lld%lld%lld", &u, &v, &w);
printf("%lld\n", 2*w%mod);
continue;
}
for(ll i = 0; i < n; i++)
tree[i].clear();
memset(sum, 0, sizeof(sum));
memset(dp, 0, sizeof(dp));
for(ll i = 0; i < n-1; i++)
{
scanf("%lld%lld%lld", &u, &v, &w);
u--,v--;
Edge t1, t2;
t1.v = v;
t1.w = w;
t2.v = u;
t2.w = w;
tree[u].push_back(t1);
tree[v].push_back(t2);
}
dfs(0, -1);
printf("%lld\n", (dp[0]%mod)*jie[n]%mod);
}
return 0;
}

纸短情长啊文章结束了但我们的故事还在继续
坚持原创技术分享,您的支持将鼓励我继续创作!