「HDU-6446」Tree and Permutation (树形DP)

发表于 | 分类于 ，

「HDU-6446」Tree and Permutation
推论+树形dp，求解树上所有点对的距离之和

题意

给定一棵树，给出树上结点1-n的全排列，求所有排列所经过的路径长度总和。

思路

对于树上的某一点对$uv$,在全排列$1-n$中相邻的情况为：

当$uv$左侧有$m$个点，右侧有$n-2-m$个点时，排列数为(注意$uv$,$vu$为两种情况)

$$2×{C}{m \choose n-2}×{A}{m \choose m}×{A}{n-2 \choose n-2}=2×(n-2)!$$

而这样的排列共有$n-1$种，即对于每一个点对，排列的总数为$2×(n-1)!$种。

此时只需要求出树上所有点对的距离之和即可，可用树形dp求解。

解法

求解树上所有点对的距离之和

要求解所有点对的距离之和，我们可以求：对于每条边，所有可能路径经过此条边的次数。

设这两条边的两边的点数分别为$s和n-s$,则这条边共经过$s×(n-s)$次,那么当前边对距离总和的贡献为$s×(n-s)×len(u,v)$,对所有边的贡献求和，即为所求解。

在一棵树中，若需要求其中任意边两端的点数，可以用一次$dfs$求解。取一点为根，记录每个节点的子节点（包含自身）个数，若子节点个数为$a[u]$,父亲一侧节点个数即为$n-a[u]$,时间复杂度为$O(n)$.

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
#include <cstdio>
#include <cstring>

using namespace std;

const int maxn=1e5+10;
const int mod=1e9+7;

int head[maxn],cnt,n;
long long son[maxn],dp[maxn];

struct Edge
{
    int nex,to,w;
}edge[20*maxn];

void add(int u,int v,int w)
{
    edge[cnt].nex=head[u];
    edge[cnt].to=v;
    edge[cnt].w=w;
    head[u]=cnt++;
}

void dfs(int u,int fa)
{
    son[u]=1;
    for(int i=head[u];~i;i=edge[i].nex)
    {
        int v=edge[i].to,w=edge[i].w;
        if(fa==v) continue;
        dfs(v,u);
        son[u]+=son[v];
        (dp[u]+=(dp[v]+(n-son[v])*son[v]%mod*w%mod)%mod)%=mod;
    }
}

int main()
{
    int u,v,w;
    while(scanf("%d",&n)!=EOF)
    {
        memset(head,0xff,sizeof(head));
        memset(dp,0,sizeof(dp));
        cnt=0;
        for(int i=1;i<n;i++)
        {
            scanf("%d%d%d",&u,&v,&w);
            add(u,v,w);
            add(v,u,w);
        }
        dfs(1,0);
        long long res=2;
        for(int i=2;i<n;i++) (res*=i)%=mod;
        printf("%lld\n",(res*dp[1])%mod);
    }
    return 0;
}