题意：
给一棵N个点的树，对应于一个长为N的全排列，对于排列的每个相邻数字a和b，他们的贡献是对应树上顶点a和b的路径长，求所有排列的贡献和。
思路：对每条边单独计算贡献，一条边B将树分成两侧，假设其中一侧大小为M，则另一侧大小为
N- M.
在N!条路线中每条都分为N - 1段，对每段单独计算贡献，例如某一-段从X到Y，则该段经过
E当且仅当X与Y在E的两侧，对应的排列数为2M(N一M)(N一2)!.共有N - 1段，假设E的长度为L，则E的贡献为2LM(N一M)(N - 1)!.
那么如何求树上各个点的距离和呢，树形dp？
可以参考这个博客:https://www.cnblogs.com/shuaihui520/p/9537214.html ；
ac代码
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int maxn = 100005; const int mod = 1e9+7; ll sum[maxn], n; ll dp[maxn]; ll b[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[cur]+sum[son])%mod;//子节点的个数 dp[cur]= ((dp[cur]+dp[son])%mod + (n-sum[son])*sum[son]%mod * len%mod)%mod; } } int main() { // freopen("in.txt","r",stdin); int u, v; ll w; b[1]=1; for(int i=2;i<=100000;i++)b[i]=i*b[i-1]%mod; while(~scanf("%d",&n)) { memset(sum, 0, sizeof(sum)); memset(dp, 0, sizeof(dp)); for(int i = 0; i < n-1; i++) { scanf("%d%d%lld", &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,0); //ll f=1; ll ans=dp[1]*b[n-1]%mod; ans=ans*2%mod; printf("%lld ",ans); for(int i = 1; i <= n; i++) tree[i].clear(); } return 0; }