题目内容

给定一棵树，根节点为 $1$ ，其中第 $u$ 个节点有点权 $a_u$ ，定义 $f(k)$ 为：

选择树上 $k$ 个互不相同的节点。你需要保证这 $k$ 个节点两两不成祖先-子孙关系。 $f(k)$ 为在所有可能的选择方案里最大的点权和。如果不存在任何一种合法的选择方案，则 $f(k)=-1$ 。

计算 $f(1),f(2),…,f(n)$ 。

【名词解释】

祖先节点：在一棵以 $u$ 为根的树中，若点 $x$ 在 $u$ 到 $v$ 的简单路径上，且 $x≠v$ 则称 $x$ 是 $v$ 的祖先节点。根节点没有祖先节点。

输入描述

每个测试文件均包含多组测试数据，第一行输入一个整数 $T(1≦T≦1000)$ 代表数据组数，每组测试数据描述如下：

第一行输入一个正整数 $n(1≦n≦5000)$ ，代表树中的节点数量。

第二行输入 $n$ 个正整数 $a_1,a_2,...,a_n(1≦a_i≦10^9)$ 表示每个节点的点权。

接下来 $n-1$ 行，第 $i$ 行插人两个正整数 $u_i,v_i(1≦u_i,v_i≦n)$ ，表示树上一条从节点 $u_i$ 到 $v_i$ 的边。输入保证是一棵合法的树。

除此之外，保证单个测试文件的 $n$ 之和不超过 $5000$ 。

输出一行 $n$ 个整数，其中第 $i$ 个整数代表 $f(i)$ 。

输入

输出

114514
5 6 9 -1