{"raw_statement":[{"iden":"statement","content":"**题目译自 [PA 2020](https://sio2.mimuw.edu.pl/c/pa-2020-1/dashboard/) Runda 2 [Sen o podboju](https://sio2.mimuw.edu.pl/c/pa-2020-1/p/sen/)**\n\n国王 Byteur，Byteotia 的统治者，目前正梦想着征服 Bitotia。就像在现实世界中一样，在他的梦中他还远远没有打败敌人。因此，他想知道他能做些什么来削弱敌国的实力……\n\n在他的梦中，Bitotia 由 $n$ 个城市（编号从 $1$ 到 $n$）组成，由 $n-1$ 条双向道路连接，可以只用这些道路从任意一个城市到达任意其他城市。换句话说，Bitotia 的地图形成了一棵树。然而，Byteur 并不记得 Bitotia 的确切道路网络……所以他的脑内生成了一个**随机**的道路网络。\n\n国王得出的结论是，强行将 Bitotia 分割成 $k$ 个小国是个好主意。Byteur 所说的划分，是指秘密地破坏正好是 $k - 1$ 条道路，这将迫使 Bitotia 分解成 $k$ 个小国，这些小国是去除选定的边后形成的连通子图。\n\n然而，对于国王来说，摧毁任何 $k-1$ 条道路都是不够的。每个 Bitotia 的城市都有一个**军事系数** $a_i$，也是由 Byteur 脑内想出来的。Byteur 知道，一个小国的军事力量越强，对 Byteotia 的威胁就越大。更准确地说：如果在一个小国，其城市的军事系数之和等于 $S$，那么来自这个小国的威胁就等于 $S^2$。对 Byteotia 的总威胁等于这 $k$ 个小国所产生的威胁之和。\n\n现在 Byteur 求助于你——他的梦想（指的是字面意思！）程序员。请帮助他，计算出 Bitotia 分裂成各州后可能产生的最小总威胁。由于 Byteur 还没有决定参数 $k$ 的值，请计算 $k$ 取从 $1$ 到 $n$（包含两端）所有值的结果。"},{"iden":"input","content":"第一行包含一个整数 $t$，表示测试点总数 ~~Byteur 做的梦的个数~~。接下来描述每一组测试点，测试点的输入格式都相同。\n\n每个测试点第一行包含一个整数 $n$。\n\n第二行包含一个长度为 $n$ 的整数序列 $a_1,a_2,\\cdots ,a_n$。\n\n接下来 $n-1$ 行是 Bitotia 的路网描述，每行两个整数 $b_i,c_i$，表示城市 $b_i,c_i$ 被一条路相连。保证输入的图是一棵树。\n\nByteur 按如下方法生成数据。首先手动选取一个整数 $t$，一个整数区间 $[n_{\\min},n_{\\max}]$ 和 $a_{\\max}$ 的值。接下来按如下步骤独立生成每个测试点：\n\n- 城市个数 $n$ 的值从 $[n_{\\min},n_{\\max}]$ 区间内均匀随机选取。\n- 每个 $a_i$ 的值从 $[1,a_{\\max}]$ 区间内独立均匀随机选取。\n- 生成一个自然数序列 $(p_1,p_2,\\cdots ,p_{n-2})$。序列中的每一个元素都是从 $[1,n]$ 区间中独立均匀随机选取的。Byteur 将其作为路网的 [Prüfer 序列](https://en.wikipedia.org/wiki/Pr%C3%BCfer_sequence)，也就是测试点中给出的树的 Prüfer 序列是 $(p_1,p_2,\\cdots,p_{n-2})$。"},{"iden":"output","content":"输出 $t$ 行，描述每个测试点的答案。每行包含 $n$ 个整数（其中 $n$ 是输入中的城市数量）；第 $k$ 个整数表示 Bitotia 在被划分为 $k$ 个小国后所能造成的最小威胁。"},{"iden":"note","content":"#### 样例 1 解释\n\n以上测试数据使用随机数种子为 $8\\ 122\\ 020$，$t=2,n_{\\min}=5,n_{\\max}=7,a_{\\max}=10$ 的参数生成。\n\n对于第一个测试案例，输出的第一个数字是 $(9+1+4+2+6+4+7)^2=1089$，代表未被分割的 Bitotia 所带来的总威胁。输出的第二个数字对应的是如果连接 $5$ 号和 $7$ 号城市的道路被摧毁的总威胁；在这种情况下，威胁将是 $(9+7)^2+(1+4+2+6+4)^2=545$。\n\n------------\n\n#### 数据生成\n\n本题的样例生成器在附件中给出。生成器将以下内容作为输入接受：生成器种子和数字 $t,n_{\\min},n_{\\max},a_{\\max}$。本题的所有测试数据都将用与之相当的生成器生成（即用不同的伪随机数库，与编译器的实现无关）。\n\n为了确保测试的随机性，每个测试点的 $t,n_{\\min},n_{\\max},a_{\\max}$ 的值都是手动选择的，生成器的种子是随机选择的。\n\n------------\n\n#### 数据范围\n\n**本题采用捆绑测试**\n\n对于 $100\\%$ 的数据，保证 $1\\le t\\le 10$，$2\\le n\\le 300$，$1\\le a_i\\le 10^6$，$1\\le b_i,c_i\\le n$，$2\\le n_{\\min}\\le n_{\\max}\\le 300$，$1\\le a_{\\max}\\le 10^6$。"}],"translated_statement":null,"sample_group":[["2\n7\n9 1 4 2 6 4 7\n1 7\n6 4\n2 3\n5 7\n3 4\n5 3\n5\n4 8 2 3 1\n4 3\n3 1\n4 2\n5 1","1089 545 371 287 227 211 203\n324 164 114 102 94"]],"show_order":[],"formal_statement":null,"simple_statement":null,"has_page_source":false}