题意：有一棵n个点的树，点之间用无向边相连。现把这棵树对应一个序列，这个序列任意两点的距离为这两点在树上的距离，显然，这样的序列有n！个，加入这是第i个序列，那么这个序列所提供的贡献值为：第一个点到其他所有点距离之和。求所有序列贡献值之和。
思路：假如第一个点是k，那么后面n-1个点共有（n - 1）！种排列，也就是说，第一个点是k那么这样的序列的贡献值为（n - 1）！*（k到其他点距离之和），显然最后答案应该是所有点之间的距离和的两倍 *（n - 1）！。问题转化为了求一棵树上所有点之间的距离，怎么求呢？
假设有一条边E，那么如果要经过E这条边，必然是两个端点在E的两边，假设左边有M点，右边有（n - M）个点，那么一共经过E次数2 *（n - M）* M，所以E的贡献长度为2 *（n - M）* M * E的权值，最后把每条边的贡献长度加在一起就是所有点之间的距离。至于求E两边点数，只要算每个点的子节点数（包括自己）就行了。
MOD值赋错了wa了一下午...写了两个版本...
标解：
参考：HDU2376Average distance(树形dp|树上任意两点距离和的平均值)
代码：
/*DP*/
#include<map>
#include<queue>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define ll long long
using namespace std;
const int maxn = + ;
const int seed = ;
const int MOD = + ;
const int INF = 0x3f3f3f3f;
struct Edge{
ll w;
int u, v, next;
}edge[maxn << ];
ll fac[maxn], dp[maxn], num[maxn], ans;
int head[maxn], tot, n;
void init(){
fac[] = ;
for(int i = ; i < maxn; i++){
fac[i] = (fac[i - ] * i) % MOD;
}
}
void addEdge(ll u, ll v, ll w){
edge[tot].u = u;
edge[tot].v = v;
edge[tot].w = w;
edge[tot].next = head[u];
head[u] = tot++;
}
void dfs(int u, int pre){
num[u] = ;
for(int i = head[u]; i != -; i = edge[i].next){
int v = edge[i].v;
ll w = edge[i].w;
if(v == pre) continue;
dfs(v, u);
num[u] += num[v];
dp[u] = (dp[u] + dp[v] + w * num[v] % MOD * (n - num[v]) % MOD) % MOD;
}
}
int main(){
init();
while(~scanf("%d", &n)){
memset(head, -, sizeof(head));
memset(dp, , sizeof(dp));
tot = ;
for(int i = ; i < n - ; i++){
ll u, v, w;
scanf("%lld%lld%lld", &u, &v, &w);
addEdge(u, v, w);
addEdge(v, u, w);
}
ans = ;
dfs(, -);
ans = dp[] * 2LL % MOD * fac[n - ] % MOD;
printf("%lld\n", ans);
}
return ;
}
/*直接代公式*/
#include<map>
#include<queue>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define ll long long
using namespace std;
const int maxn = + ;
const int seed = ;
const int MOD = + ;
const int INF = 0x3f3f3f3f;
struct Edge{
ll w;
int u, v, next;
}edge[maxn << ];
ll fac[maxn], ans;
int head[maxn], family[maxn], tot, n;
void init(){
fac[] = ;
for(int i = ; i < maxn; i++){
fac[i] = (fac[i - ] * i) % MOD;
}
}
void addEdge(ll u, ll v, ll w){
edge[tot].u = u;
edge[tot].v = v;
edge[tot].w = w;
edge[tot].next = head[u];
head[u] = tot++;
}
int dfs(int u, int pre){
family[u] = ;
for(int i = head[u]; i != -; i = edge[i].next){
if(edge[i].v == pre) continue;
family[u] += dfs(edge[i].v, u);
}
return family[u];
}
int main(){
init();
while(~scanf("%d", &n)){
memset(head, -, sizeof(head));
tot = ;
for(int i = ; i < n - ; i++){
ll u, v, w;
scanf("%lld%lld%lld", &u, &v, &w);
addEdge(u, v, w);
addEdge(v, u, w);
}
ans = ;
dfs(, -);
for(int i = ; i < tot; i += ){
ll temp;
temp = (2LL * family[edge[i].v] * (n - family[edge[i].v])) % MOD;
temp = (temp * edge[i].w) % MOD;
temp = (temp * fac[n - ]) % MOD;
ans += temp;
ans %= MOD;
}
printf("%lld\n", ans);
}
return ;
}