Codeforces 1088E Ehab and a component choosing problem
题目链接
http://codeforces.com/problemset/problem/1088/E
题目大意
给你一棵树，每个点上有权值，你需要选出来 $k$ 个联通块，使得这 $k$ 个联通块组成的点集有 $\frac{\sum\limits_{u \in s} a_u}{k}$ ，要求最大化这个值的同时，最大化 $k$。
题目分析
显然可知，有不等式 $\frac{x + y}{a + b} \leq \frac{x}{a} + \frac{y}{b}$，意味着在 $k = 1$ 的时候一定有解。可以先使用一遍树形 $DP$ 很快的将这个解求出来。那么只需要知道的是，最多有多少个联通块满足这个要求即可。此时可以使用贪心的思路，在 $DFS$ 的时候，一旦遇到大小为 $ans$ 的联通块，就把这一枝剪掉，而且显然因为 $ans$ 已经是最优解，不存在剪掉正数的一枝之后联通块的大小还等于 $ans$ 的情况。 $DFS$ 一遍统计个数即可。
代码
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <string>
#include <algorithm>
#include <vector>
using namespace std;
const int maxn = 3e5 + 5;
int n, m, t;
long long w[maxn];
vector <int> e[maxn];
long long ans;
long long cnt = 0;
long long g[maxn];
long long f[maxn];
int read(){
int x;
scanf("%d", &x);
return x;
}
int addedge(int x, int y){
e[x].push_back(y);
e[y].push_back(x);
return 0;
}
long long dfs(int x, int fa){
int y;
int i, j;
long long ret = -1e10;
g[x] = w[x];
for(i=0;i<e[x].size();i++){
y = e[x][i];
if(y != fa){
ret = max(ret, dfs(y, x));
if(g[y] > 0){
g[x] += g[y];
}
}
}
return max(g[x], ret);
}
int dfsb(int x, int fa){
int y;
int i, j;
long long ret = -1e10;
f[x] = w[x];
for(i=0;i<e[x].size();i++){
y = e[x][i];
if(y != fa){
dfsb(y, x);
if(f[y] > 0){
f[x] += f[y];
}
}
}
if(f[x] == ans){
cnt++;
f[x] = 0;
}
return 0;
}
int main(){
int i, j;
int x, y;
n = read();
for(i=1;i<=n;i++){
w[i] = read();
}
for(i=1;i<n;i++){
x = read();
y = read();
addedge(x, y);
}
ans = dfs(1, -1);
dfsb(1, -1);
printf("%lld %lld\n", ans * cnt, cnt);
return 0;
}