题目描述

题目译自 PA 2020 Runda 2 Sen o podboju

国王 Byteur，Byteotia 的统治者，目前正梦想着征服 Bitotia。就像在现实世界中一样，在他的梦中他还远远没有打败敌人。因此，他想知道他能做些什么来削弱敌国的实力……

在他的梦中，Bitotia 由 $n$ 个城市（编号从 $1$ 到 $n$）组成，由 $n-1$ 条双向道路连接，可以只用这些道路从任意一个城市到达任意其他城市。换句话说，Bitotia 的地图形成了一棵树。然而，Byteur 并不记得 Bitotia 的确切道路网络……所以他的脑内生成了一个随机的道路网络。

国王得出的结论是，强行将 Bitotia 分割成 $k$ 个小国是个好主意。Byteur 所说的划分，是指秘密地破坏正好是 $k - 1$ 条道路，这将迫使 Bitotia 分解成 $k$ 个小国，这些小国是去除选定的边后形成的连通子图。

然而，对于国王来说，摧毁任何 $k-1$ 条道路都是不够的。每个 Bitotia 的城市都有一个军事系数 $a_i$，也是由 Byteur 脑内想出来的。Byteur 知道，一个小国的军事力量越强，对 Byteotia 的威胁就越大。更准确地说：如果在一个小国，其城市的军事系数之和等于 $S$，那么来自这个小国的威胁就等于 $S^2$。对 Byteotia 的总威胁等于这 $k$ 个小国所产生的威胁之和。

现在 Byteur 求助于你——他的梦想（指的是字面意思！）程序员。请帮助他，计算出 Bitotia 分裂成各州后可能产生的最小总威胁。由于 Byteur 还没有决定参数 $k$ 的值，请计算 $k$ 取从 $1$ 到 $n$（包含两端）所有值的结果。

输入格式

第一行包含一个整数 $t$（$1 \le t \le 10$），表示测试点总数 Byteur 做的梦的个数。接下来描述每一组测试点，测试点的输入格式都相同。

每个测试点第一行包含一个整数 $n$（$2 \le n \le 300$）。

第二行包含一个长度为 $n$ 的整数序列 $a_1, a_2, \ldots, a_n$（$1 \le a_i \le 10^6$）。

接下来 $n-1$ 行是 Bitotia 的路网描述，每行两个整数 $b_i, c_i$（$1 \le b_i, c_i \le n$），表示城市 $b_i, c_i$ 被一条路相连。保证输入的图是一棵树。

数据生成方式

Byteur 按以下方法生成测试数据：

• 手动选取参数：

  • $t$（$1 \le t \le 10$）
  • 整数区间 $[n_{\min}, n_{\max}]$（$2 \le n_{\min} \le n_{\max} \le 300$）
  • $a_{\max}$（$1 \le a_{\max} \le 10^6$）

• 每个测试点独立生成：

  • 城市数量 $n$ 从 $[n_{\min}, n_{\max}]$ 中均匀随机选取。
  • 每个城市的军事系数 $a_i$ 从 $[1, a_{\max}]$ 中独立均匀随机选取。
  • 生成一个自然数序列 $(p_1, p_2, \ldots, p_{n-2})$（Prüfer 序列），序列中每个元素从 $[1, n]$ 中独立均匀随机选取，再根据该序列生成树的道路网络（即输入中给出的 $n-1$ 条道路）。

• 可在 LibreOJ 的「文件」页面找到本题的样例生成器，生成器需输入：生成器种子、$t$、$n_{\min}$、$n_{\max}$、$a_{\max}$。

• 本题所有测试数据均用类似生成器生成（仅伪随机数库可能不同，与编译器实现无关）。

• 为确保随机性，每个测试点的 $t$、$n_{\min}$、$n_{\max}$、$a_{\max}$ 均手动选择，生成器种子随机选择。

输出格式

输出 $t$ 行，描述每个测试点的答案。每行包含 $n$ 个整数（其中 $n$ 是输入中的城市数量）；第 $k$ 个整数表示 Bitotia 在被划分为 $k$ 个小国后所能造成的最小威胁。

样例

输入

2
7
9 1 4 2 6 4 7
1 7
6 4
2 3
5 7
3 4
5 3
5
4 8 2 3 1
4 3
3 1
4 2
5 1

输出

1089 545 371 287 227 211 203
324 164 114 102 94

以上测试数据使用随机数种子为 $8\,122\,020$，参数为： $t = 2$, $n_{\min} = 5$, $n_{\max} = 7$, $a_{\max} = 10$ 生成。

对于第一个测试案例，输出的第一个数字是 $(9+1+4+2+6+4+7)^2 = 1089$，代表未被分割的 Bitotia 所带来的总威胁。输出的第二个数字对应的是如果连接 $5$ 号和 $7$ 号城市的道路被摧毁的总威胁；在这种情况下，威胁将是 $(9+7)^2 + (1+4+2+6+4)^2 = 545$。