题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=6446
题目大意：对n个点建一棵树，然后问按照n的全排列的顺序进行走，问会走多远
题目思路：根据对全排列的观察，每对数字出现的次数是一样的，一对数字可以出现在n-1个位置，然后剩下n-2个数字可以乱排，)(n-2)!，一共(n-1)!，又因为树上跑dfs是对着一个方向，但实际上x-y y-x是只算了一次，所以要乘2
而这条边在图上会被几条路径经过，就需要看这条边左边几个点，右边几个点，乘一下就是一共有几种情况会经过这条边。
所以就直接用边权乘一下就可以
以下是代码：
#include <iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>using namespace std;
#define inf 0x3f3f3f3f
#define MAXN 100005
#define ll long long
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define per(i,a,b) for(int i=a;i>=b;i--)
const int MOD = 1e9+7;
struct Edge{int to,next,w;
}edge[MAXN<<1];
int tot,head[MAXN<<1],n;
ll ans,n_1;
void addedge(int u,int v,int w){edge[tot].to=v;edge[tot].w=w;edge[tot].next=head[u];head[u]=tot++;
}
int dfs(int u,int pre){int size=1;for(int i=head[u];i!=-1;i=edge[i].next){int v=edge[i].to;if(v==pre)continue;int sz=dfs(v,u);ans=(ans+(ll)((n_1*2*sz*(n-sz))%MOD)*edge[i].w)%MOD;size+=sz;}return size;
}
int main()
{int x,y,z;while(~scanf("%d",&n)){n_1=1;rep(i,2,n-1)n_1=(n_1*i)%MOD;tot=0,ans=0;memset(head,-1,sizeof(head));rep(i,1,n-1){scanf("%d%d%d",&x,&y,&z);addedge(x,y,z);addedge(y,x,z);}dfs(1,-1);//ans%=MOD;printf("%lld\n",ans);}return 0;
}