链接
http://acm.hdu.edu.cn/showproblem.php?pid=6446
题意
$n$ 个点的树形图，按照排列遍历树，求 $n!$ 个排列的总路径长。
思路
对于每条路径 $i\rightarrow j$，在所有排列中出现的总次数是 $(n-1)*(n-2)!$，
DFS 遍历所有边，每条边 $(u,v)$ 存在于 $size(v)*(n-size(v))$ 条路径中，
所以每条无向边对答案的贡献是 $2*(n-1)*(n-2)!size(v)(n-size(v))$。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
| #include <bits/stdc++.h>
#define int long long
#define SZ(x) (int)(x).size()
#define ALL(x) (x).begin(),(x).end()
#define PB push_back
#define EB emplace_back
#define MP make_pair
#define FI first
#define SE second
using namespace std;
typedef double DB;
typedef pair<int,int> PII;
typedef vector<int> VI;
typedef vector<PII> VPII;
const int N=1e5+5;
const int MOD=1e9+7;
int n,sz[N],fac[N],res;
VPII g[N];
void dfs(int u,int fa) {
sz[u]=1;
for(auto x:g[u]) {
int v=x.FI,w=x.SE;
if(v==fa) continue;
dfs(v,u);
sz[u]+=sz[v];
res=(res+sz[v]*(n-sz[v])%MOD*w%MOD)%MOD;
}
}
signed main() {
fac[0]=1;
for(int i=1;i<=100000;i++) fac[i]=fac[i-1]*i%MOD;
while(~scanf("%lld",&n)) {
for(int i=1;i<=n;i++) g[i].clear();
for(int i=1;i<n;i++) {
int u,v,w;
scanf("%lld%lld%lld",&u,&v,&w);
g[u].EB(v,w);
g[v].EB(u,w);
}
res=0;
dfs(1,0);
printf("%lld\n",res*fac[n-1]%MOD*2%MOD);
}
return 0;
}
|