HDU 6446 Tree and Permutation （樹上任意兩點距離之和，DFS，思維）

​​HDU 6446 Tree and Permutation​​

題目

給一顆 n 個節點的帶權樹樹，定義一個排列的距離為按排列順序最短路徑和。求 n 的全排列的距離和。

例如： n = 4，其中一個排列為 4 1 2 3。那麼這個排列距離為 4 -> 1 -> 2 -> 3。x ->y 指的是 x 到 y 的最短路徑。

分析

對于全排列，分析任意兩點距離對排列的貢獻。假如 n = 4：

1 2 x x

x 1 2 x

x x 1 2

那麼 1 到 2 最短距離 d12，一共出現的次數為 3 * A(2, 2) = 3 * 2!，（A 為組合數，x 位置可以随便放）。2 到 1 的同理。

是以 1，2 兩點之間最短距離在排列中出現總次數為 。

設 代表任意兩點之間最短距離和，那麼最終答案就是

現在問題轉化成為求樹上任意兩點之間距離和。對于樹上最短距離當然可以用 LCA + DFS來求，不過這種枚舉兩個節點的複雜度為 ，不能接受。。。

代碼

#include <bits/stdc++.h>
using namespace std;
#define ll long long 
#define INF 0x3f3f3f3f
#define fuck(x) cout<<x<<endl
const int N = 2e5 + 10;     // 存正反向兩次邊
const ll mod = 1e9 + 7;

int n;

int h[N], w[N], to[N], ne[N], idx;
ll fac[N], ans;

void init(){
    fac[0] = 1;
    for(int i = 1; i < N; i++){
        fac[i] = fac[i - 1] * i % mod;
    }
}

void add(int u, int v, int z){
    to[idx] = v, w[idx] = z, ne[idx] = h[u], h[u] = idx++;
}

int dfs(int rt, int from, int len){
    ll cnt = 1;
    for (int i = h[rt]; ~i; i = ne[i]){
        int v = to[i];
        if(v != from)
            cnt += dfs(v, rt, w[i]);
    }
    ans = (ans + (cnt * (n - cnt) % mod * len % mod)) % mod;
    return cnt;
}

int main(){
    init();
    while(~scanf("%d", &n)){
        memset(h, -1, sizeof(h));
        idx = 0;
        for(int i = 0, x, y, z; i < n-1; i++){
            scanf("%d%d%d", &x, &y, &z);
            add(x, y, z);
            add(y, x, z);
        }
        ans = 0;
        dfs(1, 0, 0);
        printf("%lld\n", ans * 2 % mod * fac[n - 1] % mod);
    }
    return 0;
}

/*
*/