Tree and Permutation dfs hdu 6446

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

chendu | We have carefully selected several similar problems for you: 6447 6446 6445 6444 6443

这题看懂题目之后很傻逼的

求全排列中所有1到任一点的距离之和

按边来考虑就是求贡献了

n个点 n-1条边所以每条边有（n-1)!

然后只有当要求的两个点的距离在边的两端的时候才有贡献

由于有从左到右和从右到左两种方法

所以最后每条边的贡献为 2L(n-sz[v])*sz[v] ；

 #include <cstdio>

 #include <cstring>

 #include <queue>

 #include <cmath>

 #include <algorithm>

 #include <set>

 #include <iostream>

 #include <map>

 #include <stack>

 #include <string>

 #include <vector>

 #define  pi acos(-1.0)

 #define  eps 1e-6

 #define  fi first

 #define  se second

 #define  lson l,m,rt<<1

 #define  rson m+1,r,rt<<1|1

 #define  bug         printf("******\n")

 #define  mem(a,b)    memset(a,b,sizeof(a))

 #define  fuck(x)     cout<<"["<<"x="<<x<<"]"<<endl

 #define  f(a)        a*a

 #define  sf(n)       scanf("%d", &n)

 #define  sff(a,b)    scanf("%d %d", &a, &b)

 #define  sfff(a,b,c) scanf("%d %d %d", &a, &b, &c)

 #define  sffff(a,b,c,d) scanf("%d %d %d %d", &a, &b, &c, &d)

 #define  FIN         freopen("DATA.txt","r",stdin)

 #define  gcd(a,b)    __gcd(a,b)

 #define  lowbit(x)   x&-x

 #pragma  comment (linker,"/STACK:102400000,102400000")

 using namespace std;

 typedef long long  LL;

 typedef unsigned long long ULL;

 const int INF = 0x7fffffff;

 const LL  INFLL = 0x3f3f3f3f3f3f3f3fLL;

 const int mod = 1e9 + ;

 const int maxn = 1e6 + ;

 int n, tot, head[maxn];

 LL d[maxn], sz[maxn];

 struct node {

     int v, nxt;

     LL w;

 } edge[maxn << ];

 void init() {

     tot = ;

     mem(head, -);

 }

 void add(int u, int v, LL w) {

     edge[tot].v = v;

     edge[tot].w = w;

     edge[tot].nxt = head[u];

     head[u] = tot++;

 }

 void dfs(int u, int fa) {

     sz[u] = ,d[u]=;

     for (int i = head[u]; ~i ; i = edge[i].nxt) {

         int v = edge[i].v;

         if (v == fa) continue;

         dfs(v, u);

         sz[u] += sz[v];

         d[u] = (d[u] + d[v]) % mod;

         d[u] = (d[u] + edge[i].w * sz[v] % mod * (n - sz[v]) % mod) % mod;

     }

 }

 int main() {

     while(~sf(n)) {

         init();

         for (int i =  ; i < n ; i++) {

             int u, v;

             LL w;

             scanf("%d%d%lld", &u, &v, &w);

             add(u, v, w);

             add(v, u, w);

         }

         dfs(, -);

         LL f = ;

         for (LL i =  ; i <= n -  ; i++) f = f * i % mod;

         LL ans = d[] * f *  % mod;

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

     }

     return ;

 }

巴特西

Tree and Permutation dfs hdu 6446

最新文章

热门文章