欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

cfE. Ehab and a component choosing problem(贪心)

程序员文章站 2023-11-17 22:47:10
题意 "题目链接" 给出一棵树,每个节点有权值,选出$k$个联通块,最大化 $$\frac{\sum_{i \in S} a_i}{k}$$ Sol 结论:选出的$k$个联通块的大小是一样的且都等于最大联通块的大小 证明:因为我们是在保证分数最大的情况下才去最大化$k$,一个很经典的结论是单独选择一 ......

题意

题目链接

给出一棵树,每个节点有权值,选出\(k\)个联通块,最大化

\[\frac{\sum_{i \in s} a_i}{k}\]

sol

结论:选出的\(k\)个联通块的大小是一样的且都等于最大联通块的大小

证明:因为我们是在保证分数最大的情况下才去最大化\(k\),一个很经典的结论是单独选择一个权值最大的联通块得到的分数一定是最大的,然后我们这时我们才去考虑最大化\(k\)

那么思路就很清晰了,先一遍dfs dp出最大联通块,然后再一遍dfs从下往上删就行了

#include<bits/stdc++.h>
#define int long long 
using namespace std;
const int maxn = 3e5 + 10, inf = 1e18;
inline int read() {
    char c = getchar(); int x = 0, f = 1;
    while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}
    while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
    return x * f;
}
int n, a[maxn], mx[maxn], ans = -inf, num;
#define siz(v) ((int)v.size())
vector<int> v[maxn];
void dfs(int x, int fa) {
    mx[x] = a[x];
    for(int i = 0; i < siz(v[x]); i++) {
        int to = v[x][i];
        if(to == fa) continue;
        dfs(to, x);
        mx[x] = max(mx[x], mx[x] + mx[to]);
    }
    ans = max(ans, mx[x]);
}
void dfs2(int x, int fa) {
    mx[x] = a[x];
    for(int i = 0; i < siz(v[x]); i++) {
        int to = v[x][i];
        if(to == fa) continue;
        dfs2(to, x);
        mx[x] = max(mx[x], mx[x] + mx[to]);
    }
    if(mx[x] == ans) num++, mx[x] = 0;
}
signed main() {
#ifndef online_judge
    //freopen("a.in", "r", stdin);freopen("a.out", "w", stdout);
#endif
    n = read();
    for(int i = 1; i <= n; i++) a[i] = read();
    for(int i = 1; i <= n - 1; i++) {
        int x = read(), y = read();
        v[x].push_back(y); v[y].push_back(x);
    }
    dfs(1, 0); 
    //printf("%i64d\n", ans);
    memset(mx, 0, sizeof(mx));
    dfs2(1, 0);
    cout << ans * num << " " << num;
    return 0;
}