Codeforces 1088E - Ehab and a component choosing problem

题解链接

https://lucien.ink

题目链接

https://codeforces.com/contest/1088/problem/E

题目

You're given a tree consisting of $n$ nodes. Every node $u$ has a weight $a_u$. You want to choose an integer $k$ $(1 \le k \le n)$ and then choose $k$ connected components of nodes that don't overlap (i.e every node is in at most 1 component). Let the set of nodes you chose be $s$. You want to maximize:

$$\frac{\sum\limits_{u \in s} a_u}{k}$$

In other words, you want to maximize the sum of weights of nodes in $s$ divided by the number of connected components you chose. Also, if there are several solutions, you want to maximize $k$.

Note that adjacent nodes can belong to different components. Refer to the third sample.

题意

  你有一个拥有 $n$ 个节点的树，你要选 $k$ 个联通块出来，使得这 $k$ 个联通块中所有点的权值总和 $sum$ 与联通块个数 $k$ 的比值最大，多解时应使联通块的数量尽可能地多。

思路

  考虑贪心，先求出权值和最大的联通块的权值和，记为 $max$ ，然后统计有多少个联通块的权值和与 $max$ 相等即可，显然，这样的贪心策略是最优的。

实现

https://pasteme.cn/2211

#include <bits/stdc++.h>
const int maxn = int(3e5) + 7;
int n, a[maxn], cnt;
std::vector<int> edge[maxn];
long long max = -(int(1e9) + 7);
long long dfs(int u, int pre, bool flag) {
    long long sum = a[u];
    for (int v : edge[u]) if (v != pre) sum += std::max(0ll, dfs(v, u, flag));
    if (!flag) max = std::max(max, sum);
    else if (sum == max) cnt++, sum = 0;
    return sum;
}
int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) scanf("%d", a + i);
    for (int i = 1, u, v; i < n; i++) {
        scanf("%d%d", &u, &v);
        edge[u].push_back(v);
        edge[v].push_back(u);
    }
    dfs(1, 1, false), dfs(1, 1, true);
    printf("%lld %d\n", cnt * max, cnt);
    return 0;
}