（1009) HDU 6446 Tree and Permutation(规律+树上各个点的距离和）

题意：

给一棵N个点的树，对应于一个长为N的全排列，对于排列的每个相邻数字a和b，他们的贡献是对应树上顶点a和b的路径长，求所有排列的贡献和。

分析：

经过简单的分析可以得知，全部的贡献其实相当与（这颗树上各个点的距离之和）*jichen(n-1) *2;

不相信可以举个简单的例子，或者用计算机打表可以知道；

那么如何求树上各个点的距离和呢？

可以参考这个博客:https://www.cnblogs.com/shuaihui520/p/9537214.html ；

那下面的问题就相当的简单了；

#include<bits/stdc++.h>

using namespace std;

const int maxn = ;

const int mod = 1e9+;

#define ll long long

ll sum[maxn];

int n;

ll dp[maxn];

struct no

{

    int v,w;

}t1,t2;

vector<no>tree[maxn];

void dfs(int cur, int father)

{

    sum[cur] = ;

    for(int i = ; i < tree[cur].size(); i++)

    {

        int son = tree[cur][i].v;

        ll len = tree[cur][i].w;

        if(father == son)

            continue;

        dfs(son, cur);

        sum[cur] = (sum[cur]+sum[son])%mod;

        dp[cur] = ((dp[cur]+dp[son])%mod + (n-sum[son])*sum[son]%mod * len%mod)%mod;

    }

}

ll jichen(int n)

{

    ll sum=;

    while()

    {

        if(n==)

        break;

        sum=(sum*n)%mod;

        n--;

    }

    return sum;

}

int main( )

{

    while(scanf("%d",&n)!=EOF)

    {

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

        tree[i].clear();

        memset(sum,,sizeof(sum));

        memset(dp,,sizeof(dp));

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

        {

            int u,v,w;

            scanf("%d%d%d",&u,&v,&w);

            u--;v--;

            tree[u].push_back(no{v,w});

            tree[v].push_back(no{u,w});

        }

        dfs(,-);

        printf("%lld\n",(dp[]*jichen(n-))%mod*%mod);

    }

    return ;

}

巴特西

（1009) HDU 6446 Tree and Permutation(规律+树上各个点的距离和）

题意：

最新文章

热门文章