g6-07657. 选连通块·最大化平均权值 未做

改编自 Codeforces 1088E（题面重写、数据自造；原题 URL：https://codeforces.com/problemset/problem/1088/E）

给定一棵 $n$ 个结点的树，每个结点有权值 $a_i$（可负）。选 $k$ 个互不重叠的连通块（$1\le k\le n$），记选中结点权值和为 $S$，最大化 $S/k$；若有多个方案，最大化 $k$。输出分数 $S/k$（按最简前形式写成两个整数）——但本题固定为：输出 $S$ 与 $k$ 两个整数，其中 $S=k\times M$、$k$ 为最大块数（$M$ 为最大平均值的整数形式）。

输入格式：第一行 $n$；第二行 $n$ 个权值；接下来 $n-1$ 行 $u,v$。

输出格式：一行两个整数（$S$ 与 $k$）。

输入：

3
1 2 3
1 2
1 3

输出：

6 1

（原题样例 1：整个树 $S=6,k=1$）

数据范围：$1\le n\le 3\times 10^5$，$|a_i|\le 10^9$。