@Acqua
2019-02-26T09:03:23.000000Z
字数 1414
阅读 934
动态规划
给定一棵有个结点的树，每条边有边权。记树上任意两点间最短路长度为，排列得到的权值就是。求按照每种全排列顺序在点之间走最短路得到的权值总和。（多组数据）
个数的全排列数量为个。
如果把任意相邻两个数看作一个数，那么其余个数加上就有个数，全排列数就有个。
也就是说，对于个数中任意两个数，在个数的全排列中有种全排列满足这两个数相邻（要求顺序固定为）。
再把颠倒过来变成，那么个数的全排列中，个数中任意两个数都会出现次相邻。
问题转化为计算每两点之间最短路长，计算每条边的贡献即可。
初始化：。
算法：对于每条边，贡献为。
// La Pluie#include<cstdio>#include<cstring>#include<iostream>#include<algorithm>using namespace std;typedef long long ln;const int N = 1e5 + 5, mod = 1e9 + 7;struct edge{int v; long long w; int next;} e[N << 1];int head[N], k;ln f[N] = {1}, size[N], ans, n;void adde(int u, int v, int w){e[k] = (edge){v, w, head[u]};head[u] = k++;}void dfs(int u, int f){size[u] = 1;for(int i = head[u]; i != -1; i = e[i]. next){int v = e[i]. v; ln w = e[i]. w;if(v == f) continue;dfs(v, u);ans = (ans + size[v] * (n - size[v]) % mod * w % mod) % mod;size[u] += size[v];}}int main(){for(int i = 1; i <= 100000; i++) f[i] = f[i - 1] * i % mod;while(~scanf("%lld", &n)){memset(head, -1, sizeof(head));k = 1, ans = 0;for(int i = 1; i < n; i++){int u, v; ln w;scanf("%d %d %lld", &u, &v, &w);adde(u, v, w); adde(v, u, w);}dfs(1, 0);printf("%lld\n", ans * f[n - 1] % mod * 2 % mod);}return 0;}