牛客小白月赛23G——树上求和

网址：https://ac.nowcoder.com/acm/contest/4784/G

题目描述

有一棵包含n个节点和n-1条边的树，规定树链(u,v)为树上从u到v的简单路径。
树的每条边上都有一个正整数，这个正整数被称作这条边的颜色，规定一条树链的权值w(u,v)为这条树链上所有边的颜色的代数和。
而整棵树的权值为所有不同的树链的权值的代数和。
已知所有边的颜色集合恰好为1到n-1这n-1个不同的正整数，请你为每条边安排一种颜色，使得这棵树的权值尽量小，你不需要给出具体方案，只需要求出这个最小的权值即可。

输入描述:

测试数据第一行，是一个正整数n(1≤n≤10^5)，表示树的节点个数
接下来n-1行，每行两个用空格隔开的整数u,v，表示树上有一条边连接u和v
###　输出描述:
一个整数，表示了这棵树的最小的权值。
###　输入
4
1 2
2 3
3 4
###　输出
19

说明

w(1,2)+w(1,3)+w(1,4)+w(2,3)+w(2,4)+w(3,4)
=3+4+6+1+3+2
=19

题解：

每条边被计算的数目等于这条边两边的节点的个数之积。
然后按照积这个权值进行排序。然后依次赋值1，2 ，，，，n-1

AC代码：

#include<iostream>
#include<cstring>
#include<algorithm>
#include<vector>
using namespace std;
#define ll long long int
const ll maxn=1e5+10;
vector<ll>q[maxn];
ll n,a,b;
vector<ll>p; 
ll dfs(ll u,ll v){
    ll sum=1;//这里很重要 
    for(int i=0;i<q[u].size();i++){
        if(q[u][i]!=v)
            sum+=dfs(q[u][i],u);
    }
    p.push_back(sum*(n-sum));
    return sum;
}
int main(){
    cin>>n;
    for(int i=1;i<n;i++){
        cin>>a>>b;
        q[a].push_back(b);
        q[b].push_back(a);
    }
    dfs(1,-1); 
    sort(p.begin(),p.end());
    ll s=0,l=n-1;
    for(int i=1;i<p.size();i++){
        s+=(p[i]*l);
        l--;
    }
    cout<<s<<endl;
    return 0;
} 

这道题的dfs值得多看看

打卡第15天。2020/03/26