HDU6446（树上、排列的贡献计算）

关键点在于：全排列中，任意两点u、v相邻的次数一定是(n - 1)! * 2次，即一个常数（可以由高中数学知识计算，将这两个点捏一起然后全排列然后乘二；或者用n! / C(2, n)）。

这之后就好算了，每条边算一下子树size对吧，乘法原理就是贡献次数，乘以边权加一起就行了。

所以不是dfs就行了吗，跟dp有啥关系……

PS：变量名起的不行，不该叫inv，而是fac，代表阶乘

 const int maxn = 1e5 + ;

 const int mod = 1e9 + ;

 int n, tot;

 int size[maxn];

 struct Edge {

     int to, nxt;

     ll cost;

 }e[maxn << ];

 int head[maxn];

 ll inv[maxn], f[maxn], ans;

 inline void add(int u, int v, ll cost) {

     e[++tot].to = v, e[tot].cost = cost, e[tot].nxt = head[u], head[u] = tot;

 }

 inline void dfs(int cur, int fa) {

     size[cur] = ;

     for (int i = head[cur]; i; i = e[i].nxt) {

         int son = e[i].to;

         if (son == fa)  continue;

         f[son] = e[i].cost;

         dfs(son, cur);

         size[cur] += size[son];

     }

     if (fa) ans = (ans + (ll)(n - size[cur]) * size[cur] % mod * f[cur] % mod) % mod;

 }

 int main() {

     inv[] = ;

     rep(i, , maxn - )    inv[i] = inv[i - ] * i % mod;

     while (~scanf("%d", &n)) {

         ans = tot = ;

         rep(i, , n)    head[i] = ;

         rep(i, , n - ) {

             int u, v;

             ll cost;

             read(u), read(v), read(cost);

             add(u, v, cost), add(v, u, cost);

         }

         dfs(, );

         writeln(ans * inv[n - ] % mod *  % mod);

     }

     return ;

 }

巴特西

HDU6446（树上、排列的贡献计算）

最新文章

热门文章