2018 CCPC 网络赛I题(HDU 6446) 题解

izcat 2018-08-26 原文

// 昨天打了一场网络赛，表现特别不好，当然题目难度确实影响了发挥，但还是说明自己太菜了，以后还要多多刷题。

I – Tree and Permutation

简单说明一下题意，给出一个1,2,3…N的排列，显然全部共有N!种排列，每种排列的数字代表树上的一个结点，设Pi是其中第i种排列的相邻数字表示的结点的距离之和，让我们求sum(Pi)(1<=i<=N!)。

可以设dis(i, j)为树上任意两点间的最短距离，稍加分析一下容易得到所求答案为 (N-1)! * sum(dis(i, j))。对于dis(i, j)很容易想到用Floyd来求，但题目数据量为1e5显然O(n^3)算法肯定超时。由于这是一棵树，dis(i, j)的最短路径是唯一的（不存在环），那么对于相邻结点u, v，可以发现边(u, v)走过的次数为左边结点数量*右边结点数量。现在大概就是一道树形dp的题了，剩下的就是代码实现了。

// 比赛的时候用的vector存邻接矩阵，搞了半天用map<pair<int,int>, int>存dis(u,v)，交上去一直TLE，不明白怎么回事，昨晚调了半天又一直ML(Memory Limit)

// 上网查了一下说是vector跟map内存没有释放什么的，反正到现在还没弄明白。。。以后还是用链式前向星吧

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

const int maxn = 100010;
const int mod = 1e9+7;

int head[maxn], cnt;
struct Edge{
    int to, nxt, w;
    Edge(){}
    Edge(int _to, int _nxt, int _w): to(_to), nxt(_nxt), w(_w){}
};
Edge edge[maxn*2];

int n, child[maxn];
long long ans;
long long fact[maxn];
void pre()
{
    fact[0] = 1;
    for(int i=1;i<maxn;i++)
        fact[i] = fact[i-1] * i % mod;
}

void init()
{
    cnt = 0;
    memset(head, -1, sizeof(head));
    memset(child, 0, sizeof(child));
}

void add(int from, int to, int weight)
{
    edge[cnt] = Edge(to, head[from], weight);
    head[from] = cnt++;
}

void dfs(int u, int fa)
{
    child[u] = 1;
    for(int i=head[u];~i;i=edge[i].nxt)
    {
        int v = edge[i].to;
        if(v!=fa)
        {
            dfs(v, u);
            child[u] += child[v];
            ans += (long long)child[v]*(n-child[v])*edge[i].w%mod;
            if(ans>mod) ans -= mod;
        }
    }
}

int main()
{
    pre();

    int u, v, dis;
    while(~scanf("%d", &n))
    {
        init();
        for(int i=1;i<n;i++)
        {
            scanf("%d %d %d", &u, &v, &dis);    
            add(u, v, dis);
            add(v, u, dis);
        }
        
        ans = 0;
        dfs(1, -1);
        printf("%lld\n", 2*ans*fact[n-1]%mod);
    
    }
    return 0;
}