Description
给定一棵 (n) 个节点的树，点有点权 (a_u)，可能为负。现在请你在树上找出 (k~(1~leq~k~leq~n)) 个不相交集合，使得每个集合中的每对点都可以通过本集合中的点互相到达，假设选出的 (k) 个集合的并集为 (s)，要求最大化：
如果有多解请输出 (k) 最大的解
Input
第一行是节点个数 (n)。
下面一行 (n) 个数代表点权
下面 (n - 1) 行描述这棵树
Output
输出一行两个整数，分别是选出的点权和以及 (k)
不约分
Solution
结论：在不限元素个数时，要求选出元素的平均值最大，则最优解一定为只选择元素值最大的元素。如果有多个元素的值最大，选择个数对答案无影响。
证明：数学归纳法，先将元素按照权值降序排序。当只选择 (1) 个元素的时候，显然选择第一个元素最优。考虑已经选了 (k) 个元素，现在要决定是否选 (k + 1) 个元素。由于是降序排序的，则这个元素的权值显然不大于前面所有元素的平均值。设前面所有元素的平均值为 (a)，第 (k + 1) 个元素的权值为 (w)，则选择该元素后的平均值为 (frac{ak + w}{k + 1}) 。要判断它和原平均值 (a) 的关系，则对它们做差，记 (delta~=~frac{ak + w}{k + 1} - a)
则
前面已经论证 (w~leq~a)，于是 (delta~leq~0)。当且仅当 (w~=~a) 即前 (k + 1) 个元素权值相同时，等号成立。证毕。
于是根据这个结论，问题就被转化成了：求一个符合要求的集合使得这个集合的权值和尽可能大，然后统计有多少个这样的不想交的集合。
第一问显然可以直接树形DP，设 (f_u) 为 (u) 的子树中必选 (u) 的集合的最大权值，则有：
于是就可以求出最大的权值了。考虑统计答案时，由于要求的是不相交的集合，所以我们每将一个集合加入贡献以后再将这个集合删掉，一边统计答案一遍DP就可以了。
Code
#include <cstdio>
#include <algorithm>
#ifdef ONLINE_JUDGE
#define freopen(a, b, c)
#define putchar(o)
puts("I am a cheater!")
#endif
#define rg register
#define ci const int
#define cl const long long
typedef long long int ll;
namespace IPT {
const int L = 1000000;
char buf[L], *front=buf, *end=buf;
char GetChar() {
if (front == end) {
end = buf + fread(front = buf, 1, L, stdin);
if (front == end) return -1;
}
return *(front++);
}
}
template <typename T>
inline void qr(T &x) {
rg char ch = IPT::GetChar(), lst = ' ';
while ((ch > '9') || (ch < '0')) lst = ch, ch=IPT::GetChar();
while ((ch >= '0') && (ch <= '9')) x = (x << 1) + (x << 3) + (ch ^ 48), ch = IPT::GetChar();
if (lst == '-') x = -x;
}
template <typename T>
inline void ReadDb(T &x) {
rg char ch = IPT::GetChar(), lst = ' ';
while ((ch > '9') || (ch < '0')) lst = ch, ch = IPT::GetChar();
while ((ch >= '0') && (ch <= '9')) x = x * 10 + (ch ^ 48), ch = IPT::GetChar();
if (ch == '.') {
ch = IPT::GetChar();
double base = 1;
while ((ch >= '0') && (ch <= '9')) x += (ch ^ 48) * ((base *= 0.1)), ch = IPT::GetChar();
}
if (lst == '-') x = -x;
}
namespace OPT {
char buf[120];
}
template <typename T>
inline void qw(T x, const char aft, const bool pt) {
if (x < 0) {x = -x, putchar('-');}
rg int top=0;
do {OPT::buf[++top] = char(x % 10 + '0');} while (x /= 10);
while (top) putchar(OPT::buf[top--]);
if (pt) putchar(aft);
}
const int maxn = 300010;
const int maxm = 600010;
struct Edge {
int to;
Edge *nxt;
};
Edge edge[maxm], *hd[maxn];int ecnt;
inline void cont(ci from, ci to) {
Edge &e = edge[++ecnt];
e.to = to; e.nxt = hd[from]; hd[from] = &e;
}
int n, cnt;
ll ans = -(1ll << 62);
ll MU[maxn], frog[maxn];
void reading();
void dfs(ci, ci, ci);
int main() {
freopen("1.in", "r", stdin);
qr(n);
for (rg int i = 1; i <= n; ++i) qr(MU[i]);
reading();
dfs(1, 0, 1); dfs(1, 0, 0);
qw(ans * cnt, ' ', true); qw(cnt, '
', true);
return 0;
}
void reading() {
int a, b;
for (rg int i = 1; i < n; ++i) {
a = b = 0; qr(a); qr(b);
cont(a, b); cont(b, a);
}
}
void dfs(ci u, ci fa, ci op) {
frog[u] = MU[u];
for (Edge *e = hd[u]; e; e = e->nxt) {
int &to = e->to;
if (to == fa) continue;
dfs(to, u, op);
if (frog[to] > 0) frog[u] += frog[to];
}
if (op) ans = std::max(ans, frog[u]);
else if (frog[u] == ans) ++cnt, frog[u] = -(1ll << 60);
}
Summary
选择任意个元素使得平均值最大时，只选择最大的就好啦