P17878 中位树 / median

给定一棵有 $n$ 个节点的无根树，节点编号为 $1,2,\ldots,n$，其中节点 $i$ 的权值为 $w_i$。 你可以选择一个非负整数 $k$，满足 $2k\le n-1$，并删除树上 $2k$ 条不同的边。删除这些边后，树被分成 $2k+1$ 个连通块。可以选择 $k=0$，此时不删除任何边。 定义一个连通块的权值为该连通块内所有节点的权值之和。将所得 $2k+1$ 个连通块的权值按从小到大的顺序排列，记为 $a_1\le a_2\le\cdots\le a_{2k+1}$，则这些连通块权值的中位数为 $a_{k+1}$。 你需要选择 $k$ 以及删除的边，使所得连通块权值的中位数最大。请求出这个最大值。

**本题包含多组测试数据。** 输入的第一行包含两个整数 $c,t$，分别表示测试点编号与测试数据组数。特别地，若 $c=0$，则该测试点为样例。 接下来依次输入 $t$ 组测试数据。对于每组测试数据： - 输入的第一行包含一个正整数 $n$，表示树的节点数。 - 第二行包含 $n$ 个整数 $w_1,w_2,\ldots,w_n$，表示各节点的权值。 - 接下来 $n-1$ 行，每行包含两个正整数 $u_i,v_i$，表示树上有一条连接节点 $u_i$ 和 $v_i$ 的边。

对于每组测试数据，输出一行一个整数，表示所得连通块权值的中位数的最大值。

**【样例 1 解释】** 对于第一组测试数据，选择 $k=2$，删除全部 $4$ 条边。所得连通块的权值从小到大依次为 $-10,-10,4,4,4$，中位数为 $4$。可以证明，不存在中位数更大的合法方案。 对于第二组测试数据，选择 $k=0$，不删除任何边。唯一的连通块的权值为 $11$，其中位数也为 $11$。这是最优方案。 对于第三组测试数据，选择 $k=1$，删除连接节点 $1,2$ 的边和连接节点 $1,5$ 的边。所得三个连通块的节点集合分别为 $\{1,9,10\}$、$\{2,3,4\}$ 和 $\{5,6,7,8\}$，权值从小到大依次为 $-50,12,12$，中位数为 $12$。这是最优方案。 **【样例 2】** 见题目目录下的 `median/median2.in` 与 `median/median2.ans`。 该样例满足测试点 $2\sim4$ 的约束条件。 **【样例 3】** 见题目目录下的 `median/median3.in` 与 `median/median3.ans`。 该样例满足测试点 $5,6$ 的约束条件。 **【样例 4】** 见题目目录下的 `median/median4.in` 与 `median/median4.ans`。 该样例满足测试点 $13$ 的约束条件。 **【样例 5】** 见题目目录下的 `median/median5.in` 与 `median/median5.ans`。 该样例满足测试点 $14,15$ 的约束条件。 **【样例 6】** 见题目目录下的 `median/median6.in` 与 `median/median6.ans`。 该样例满足测试点 $16,17$ 的约束条件。 **【数据范围】** 设 $N$ 为单个测试点内所有测试数据的 $n$ 的和。对于所有测试数据，均有： - $0\le c\le 20$，$1\le t\le 10^3$； - $3\le n\le 10^5$，$N\le 3\times 10^5$； - 对于所有 $1\le i\le n$，均有 $|w_i|\le 10^{13}$； - 对于所有 $1\le i\le n-1$，均有 $1\le u_i,v_i\le n$； - 给出的边构成一棵树。 ::cute-table{tuack} |测试点编号|$n\le$|$N\le$|特殊性质| |:----:|:----:|:----:|:----:| |$1$|$16$|$100$|无| |$2\sim4$|$100$|$500$|A| |$5,6$|^|^|无| |$7,8$|$800$|$4\,000$|A| |$9,10$|^|^|无| |$11,12$|$30\,000$|$10^5$|A| |$13$|$10^5$|$3\times10^5$|^| |$14,15$|^|^|B| |$16,17$|^|^|C| |$18$|$30\,000$|$10^5$|无| |$19,20$|$10^5$|$3\times10^5$|^| 特殊性质 A：对于所有 $1\le i\le n-1$，均有 $u_i=i$，$v_i=i+1$。 特殊性质 B：对于所有 $1\le i\le n-1$，均有 $u_i=1$。 特殊性质 C：对于所有 $1\le i\le n$，均有 $w_i\le0$。