2018 CCPC网络赛1009 Tree and Permutation (HDU6446)(dfs or 树形dp)

谁践踏了优雅 2021-09-16 05:10 218阅读 0赞

Tree and Permutation  
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)  
Total Submission(s): 169 Accepted Submission(s): 57

Problem Description  
There are N vertices connected by N−1 edges, each edge has its own length.  
The set \{ 1,2,3,…,N \} contains a total of N! unique permutations, let’s say the i-th permutation is Pi and Pi,j is its j-th number.  
For the i-th permutation, it can be a traverse sequence of the tree with N vertices, which means we can go from the Pi,1-th vertex to the Pi,2-th vertex by the shortest path, then go to the Pi,3-th vertex ( also by the shortest path ) , and so on. Finally we’ll reach the Pi,N-th vertex, let’s define the total distance of this route as D(Pi) , so please calculate the sum of D(Pi) for all N! permutations.

Input  
There are 10 test cases at most.  
The first line of each test case contains one integer N ( 1≤N≤105 ) .  
For the next N−1 lines, each line contains three integer X, Y and L, which means there is an edge between X-th vertex and Y-th of length L ( 1≤X,Y≤N,1≤L≤109 ) .

Output  
For each test case, print the answer module 109+7 in one line.

Sample Input  
3  
1 2 1  
2 3 1  
3  
1 2 1  
1 3 2

Sample Output  
16  
24

**题意**  
给出一颗树，按节点进行全排列，以全排列的第一个数为根节点，求出根节点到其他点的最短路径之和(说是最短路径，仔细想想(**题目说了**)就是树的节点之间的距离)，然后整个再求一次和  
**题解**  
官方题解的方法比较简单，这里是我队比赛时AC的思路，首先队友读题，发现问题可以变成所有点能到达的距离和乘(n−1)!  ( n − 1 ) ! (简单的排列问题)，队友把求和丢给我，然后我开始了自闭之旅，辜负了队友的希望，还好最后挽回了一点颜面,A了这题。  
这里说一下我求和的思路，  
第一遍dfs可以求出点1(**随便选个点当根**)的答案，存下以一个点为根的子树的答案和子树包含的节点数量。  
第二遍dfs就可以根据  
ans2\[v\]=ans1\[v\]\+(ans2\[u\]−ans1\[v\]−chi\[v\]∗w)\+(n−chi\[v\])∗w  a n s 2 \[ v \] = a n s 1 \[ v \] + ( a n s 2 \[ u \] − a n s 1 \[ v \] − c h i \[ v \] ∗ w ) + ( n − c h i \[ v \] ) ∗ w 求出最终的值

#include <bits/stdc++.h>
    using namespace std;
    #define rep(i,a,n) for (int i=a;i<n;i++)
    #define per(i,a,n) for (int i=n-1;i>=a;i--)
    #define pb push_back
    #define mp make_pair
    #define all(x) (x).begin(),(x).end()
    #define fi first
    #define se second
    #define SZ(x) ((int)(x).size())
    typedef vector<int> VI;
    typedef long long ll;
    typedef pair<int,int> PII;
    const ll mod=1000000007;
    ll powmod(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){
       if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
    ll gcd(ll a,ll b) { return b?gcd(b,a%b):a;}
    const int maxn = 100010;
    vector<pair<int,ll>> e[maxn];
    int vis[maxn];
    
    
    ll ans1[maxn], ans2[maxn], chi[maxn];
    ll ans;
    int n;
    void dfs1(int u)
    {
        vis[u] = 1;
        chi[u] = 0;
        for(auto &v:e[u])
        {
            if(!vis[v.first])
            {
                dfs1(v.first);
                chi[u] += chi[v.first];
                ans1[u] +=  ans1[v.first]%mod + chi[v.first]%mod*v.second%mod;
                ans1[u]  %= mod;
            }
        }
        chi[u]++;
    }
    
    
    void dfs2(int u)
    {
        if (u == 1)
            ans2[u] = ans1[u];
        vis[u] = 1;
        for(auto &v:e[u])
        {
            if(!vis[v.first])
            {
                ans2[v.first] = (ans1[v.first]%mod + (ans2[u]%mod - ans1[v.first]%mod - chi[v.first]%mod*v.second%mod + mod + mod)%mod + (n - chi[v.first])%mod*v.second%mod + mod)%mod;
                dfs2(v.first);
            }
        }
    }
    
    int main()
    {
    
        while(scanf("%d", &n)!=EOF)
        {
        rep(i,1,n+1)
        {
            e[i].clear();
            vis[i] = 0;
            ans1[i] = 0;
            ans2[i] = 0;
        }
        rep(i,1,n)
        {
            int u,v;
            ll w;
            scanf("%d%d%lld",&u,&v,&w);
            e[u].push_back(make_pair(v,w));
            e[v].push_back(make_pair(u,w));
        }
        ans = 0;
        dfs1(1);
        memset(vis, 0, sizeof(vis));
        dfs2(1);
        rep(i,1,n+1)
            {
                ans += ans2[i];
                ans %= mod;
            }   
        if(n == 1)
            printf("0\n");
        else if(n == 2)
        {
            printf("%lld\n",ans%mod);
        }   
        else
        {
            ll t = 1;
            rep(i,1,n)
            {
                t *= i;
                t %= mod;
            }
            ans = ans%mod*t%mod;
            printf("%lld\n", ans %mod);
        }  
        }
        return 0;
    }

**最后，这真是一场打的十分难受的网络赛！！！**  
[如何评价2018年ccpc网络赛？][2018_ccpc]

[2018_ccpc]: https://www.zhihu.com/question/291833145