题意：

给一棵N个点的树，对应于一个长为N的全排列，对于排列的每个相邻数字a和b，他们的贡献是对应树上顶点a和b的路径长，求所有排列的贡献和。

分析：

经过简单的分析可以得知，全部的贡献其实相当与（这颗树上各个点的距离之和）*jichen(n-1) *2; 

不相信可以举个简单的例子，或者用计算机打表可以知道；

那么如何求树上各个点的距离和呢？

可以参考这个博客: ； 

那下面的问题就相当的简单了；

#include
      
       using namespace std;const int maxn = 100001;const int mod = 1e9+7;#define ll long longll sum[maxn];int n;ll dp[maxn];struct no{    int v,w;}t1,t2;vector
       
        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;    }}ll jichen(int n){    ll sum=1;    while(1)    {        if(n==1)        break;        sum=(sum*n)%mod;        n--;    }    return sum;}int main( ){    while(scanf("%d",&n)!=EOF)    {        for(int i=0 ; i<=n ; i++)        tree[i].clear();        memset(sum,0,sizeof(sum));        memset(dp,0,sizeof(dp));        for(int i = 0 ; i