7.17每日一题题解

树上求和

• 题目链接：https://ac.nowcoder.com/acm/contest/4784/G

涉及知识点：

• 贪心
• 图论
• dfs

solution：

• 我们只需要计算出每条边被经历过了多少次
• 每条边被经过的次数等于这条边分隔开的两端点分别所在的连通块大小相乘
• 然后把这些次数按照从小到达或者从大到小排序
• 我是从小到大，那么次数小的边就应该赋值为（n - i + 1）

std:

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

typedef long long LL;
const int N = 1e5 + 10;
vector<int>v[N];
LL son[N];
int n;
void dfs(int u,int f)
{
    int sum = 0;
    
    for(auto &x : v[u])
    {
        if(x == f){
            continue;
        }
        dfs(x,u);
        sum += son[x];
    }
    son[u] = sum + 1;
}

int main()
{
    cin >> n;
    for(int i = 0;i < n - 1;i ++)
    {
        int a,b;
        cin >> a >> b;
        v[a].push_back(b);
        v[b].push_back(a);
    }
    
    dfs(1,0);
    
    for(int i = 1;i <= n;i ++)    
    {
        son[i] = (n - son[i]) * son[i];
    }
    
    sort(son + 1,son + n + 1);
    LL ans = 0;
    for(int i = 1;i <= n;i ++)
    {
        ans += (n - i + 1) * son[i];
    }
    
    cout << ans << endl;
    
    return 0;
}