hdu6446 Tree and Permutation（树形dp）

题意：

给定n个点的树，树边有边权
对于一个长度为n的排列，它的权值为排列中所有相邻数在树上的距离和，
问长度为n的所有不同排列的权值和是多少,答案对1e9+7取模

数据范围：n<=1e5

解法：

长度为n的排列显然有n-1个相邻点对.
长度为n的全排列有n!种,那么共(n-1)*n!个相邻点对
而每种点对出现的次数显然相同,
有序点对共n*(n-1)种,那么每种出现(n-1)*n!/(n*(n-1))=(n-1)!次
对于树上每条边,统计有多少个点对经过,计算贡献即可.
复杂度是O(n)的

code：

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define PI pair<int,int>
const int maxm=1e5+5;
const int mod=1e9+7;
vector<PI>g[maxm];
int fac[maxm];
int sz[maxm];
int ans;
int n;
void dfs(int x,int fa){
    sz[x]=1;
    for(auto i:g[x]){
        int v=i.first;
        if(v==fa)continue;
        int w=i.second;
        dfs(v,x);
        sz[x]+=sz[v];
        ans+=fac[n-1]*w%mod*(n-sz[v])%mod*sz[v]%mod*2%mod;//*2是因为点对是有序的
        ans%=mod;
    }
}
signed main(){
    ios::sync_with_stdio(0);
    fac[0]=1;
    for(int i=1;i<maxm;i++){
        fac[i]=fac[i-1]*i%mod;
    }
    while(cin>>n){
        for(int i=1;i<=n;i++)g[i].clear();
        for(int i=1;i<n;i++){
            int a,b,c;cin>>a>>b>>c;
            g[a].push_back({b,c});
            g[b].push_back({a,c});
        }
        ans=0;
        dfs(1,1);
        cout<<ans<<endl;
    }
    return 0;
}

---

本文地址：https://blog.csdn.net/weixin_44178736/article/details/108126235