HDU - 6446 Tree and Permutation

传送门：http://acm.hdu.edu.cn/showproblem.php?pid=6446

本题是一个树上的问题——DFS。

一棵N个结点的树，其结点为1~N。树具有N-1条边，每一条边具有一个权值。

1~N具有N!个不同的排列，第i（1≤i≤N!）个排列记为P[i]，第i个排列中的第j（1≤j≤N）个数记为P[i][j]。

对于第i个排列P[i]，在树上沿最短路依次通过P[i][1]~P[i][N]。记最短路的权值和为S[i]，求解：

$\sum_{i=1}^{N!} S_i \mod M$

考虑1~N间的两个不同的数u、v。在N!个排列中，v恰好为u的后继的排列数为(N-1)!。于是，若记u→v的最短路为D(u,v)，则所求答案为：

$(N-1)!\:*\sum_{u\ne v}D(u,v)\mod M$

现在，考虑式：

$f(T)=\sum_{u<v}D(u,v)\cdots(*)$

接下来，考虑树的结点与边。无向树上的每一个结点都是树的割顶，每一条边都是树的桥。于是，树上的每一条边将树划分为两棵子树。考虑连接结点u、v的边：这条边将树划分为以结点u为根的子树、和以结点v为根的子树。设以结点u为根的子树的结点数为cnt[u]，则以结点v为根的子树的结点数为cnt[v]=N-cnt[u]。

回到式（*）中，则边(u,v)对式子的贡献为$w(u,v)*cnt[u]*cnt[v]$。

考虑通过DFS预处理cnt[]：选取某一个结点作为根结点，通过DFS预处理以结点u为根的子树的结点数cnt[u]。之后，遍历树上的边：连接结点v与其父结点的边，其对式子的贡献为$w(p[v],v)*cnt[v]*(N-cnt[v])$。

考虑到双向，答案为$ans=2(N-1)!\:*f(T)\mod M$。

参考程序如下：

#include <bits/stdc++.h>

using namespace std;

#define MAX_N 100005

const int64_t mod = 1e9 + ;

struct arrow

{

    int to;

    int cost;

    arrow(int to = , int cost = ) : to(to), cost(cost) {}

};

int64_t fact[MAX_N];

void init(void)

{

    fact[] = ;

    for (int i = ; i < MAX_N; i++) fact[i] = fact[i - ] * i % mod;

}

int n;

vector<arrow> adj[MAX_N];

int64_t ans;

int cnt[MAX_N];

void dfs_cnt(int u, int p)

{

    cnt[u] = ;

    for (int i = ; i < adj[u].size(); i++) {

        int v = adj[u][i].to;

        if (v == p) continue;

        dfs_cnt(v, u);

        cnt[u] += cnt[v];

    }

}

void dfs_calc(int u, int p)

{

    for (int i = ; i < adj[u].size(); i++) {

        int v = adj[u][i].to;

        int w = adj[u][i].cost;

        if (v == p) continue;

        int64_t cur = 1ll * cnt[v] * (n - cnt[v]);

        ans += cur * w % mod;

        ans %= mod;

        dfs_calc(v, u);

    }

}

int main(void)

{

    ios::sync_with_stdio(false);

    init();

    while (cin >> n) {

        memset(cnt, , sizeof(cnt));

        for (int i = ; i < n; i++) {

            int u, v, w;

            cin >> u >> v >> w;

            adj[u].push_back(arrow(v, w));

            adj[v].push_back(arrow(u, w));

        }

        ans = ;

        dfs_cnt(, -);

        dfs_calc(, -);

        cout << 2ll * ans % mod * fact[n - ] % mod << endl;

        for (int i = ; i <= n; i++) adj[i].clear();

    }

    return ;

}

巴特西

HDU - 6446 Tree and Permutation

最新文章

热门文章