Title Link: click here

 

Solutions:

Consider the contribution times of u and v to the answer, because they are all permutations, then u and v can be placed at 1, 2, 2.3... There are (n-1) positions, and the reverse order is (n-1 * 2), and then other n-2 points can be arranged at will, that is, (n-2)!, so the contribution times of any side is 2*(n-1)!

So the problem becomes to find the path sum of any two points. In this problem, the contribution of no edge is to use this line to divide the tree node into two parts. Then the contribution times of this edge is the product of these two parts, and we can use dfs to find the tree size.

 

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