P9096 [PA 2020] Dream of Conquest

**This problem is translated from [PA 2020](https://sio2.mimuw.edu.pl/c/pa-2020-1/dashboard/) Round 2 [Sen o podboju](https://sio2.mimuw.edu.pl/c/pa-2020-1/p/sen/).** King Byteur, the ruler of Byteotia, is currently dreaming of conquering Bitotia. Just like in the real world, in his dream he is still far from defeating the enemy. Therefore, he wants to know what he can do to weaken the enemy country... In his dream, Bitotia consists of $n$ cities (numbered from $1$ to $n$), connected by $n-1$ bidirectional roads, and using only these roads it is possible to travel from any city to any other city. In other words, the map of Bitotia forms a tree. However, Byteur does not remember the exact road network of Bitotia... so his mind creates a **random** road network. The king concludes that it is a good idea to force Bitotia to split into $k$ smaller countries. By a split, Byteur means secretly destroying exactly $k - 1$ roads, which will force Bitotia to decompose into $k$ smaller countries. These smaller countries are the connected subgraphs formed after removing the selected edges. However, for the king, destroying just any $k-1$ roads is not enough. Each city of Bitotia has a **military coefficient** $a_i$, also imagined by Byteur. Byteur knows that the stronger the military power of a smaller country, the greater the threat it poses to Byteotia. More precisely: if, in a smaller country, the sum of military coefficients of its cities equals $S$, then the threat from this country equals $S^2$. The total threat to Byteotia equals the sum of threats produced by these $k$ smaller countries. Now Byteur asks you—his dream (literally!) programmer—for help. Please help him compute the minimum possible total threat after splitting Bitotia into countries. Since Byteur has not yet decided the value of the parameter $k$, compute the result for all $k$ from $1$ to $n$ (inclusive).

The first line contains an integer $t$, the number of test cases ~~the number of dreams Byteur has~~. Each test case is described in the same format as follows. The first line of each test case contains an integer $n$. The second line contains an integer sequence $a_1,a_2,\cdots ,a_n$ of length $n$. The next $n-1$ lines describe the road network of Bitotia. Each line contains two integers $b_i,c_i$, meaning that cities $b_i$ and $c_i$ are connected by a road. It is guaranteed that the input graph is a tree. Byteur generates the data in the following way. First, he manually chooses an integer $t$, an integer interval $[n_{\min},n_{\max}]$, and a value $a_{\max}$. Then, each test case is generated independently by the following steps: - The number of cities $n$ is chosen uniformly at random from the interval $[n_{\min},n_{\max}]$. - Each $a_i$ is chosen independently and uniformly at random from the interval $[1,a_{\max}]$. - Generate a sequence of natural numbers $(p_1,p_2,\cdots ,p_{n-2})$. Each element of the sequence is chosen independently and uniformly at random from $[1,n]$. Byteur uses it as the [Prüfer sequence](https://en.wikipedia.org/wiki/Pr%C3%BCfer_sequence) of the road network, i.e., the Prüfer sequence of the tree given in the test case is $(p_1,p_2,\cdots,p_{n-2})$.

Output $t$ lines, describing the answers for each test case. Each line contains $n$ integers (where $n$ is the number of cities in the input). The $k$-th integer denotes the minimum threat Bitotia can cause after being split into $k$ smaller countries.

#### Explanation of Sample 1 The above testdata was generated using random seed $8\ 122\ 020$, with parameters $t=2,n_{\min}=5,n_{\max}=7,a_{\max}=10$. For the first test case, the first number in the output is $(9+1+4+2+6+4+7)^2=1089$, which represents the total threat caused by Bitotia when it is not split. The second number in the output corresponds to the total threat if the road connecting cities $5$ and $7$ is destroyed; in this case, the threat is $(9+7)^2+(1+4+2+6+4)^2=545$. ------------ #### Data Generation The sample generator for this problem is provided in the attachment. The generator takes the following as input: the generator seed and the numbers $t,n_{\min},n_{\max},a_{\max}$. All testdata for this problem will be generated using an equivalent generator (i.e., using a different pseudo-random library and independent of the compiler implementation). To ensure randomness of the tests, the values of $t,n_{\min},n_{\max},a_{\max}$ for each test case are chosen manually, and the generator seed is chosen randomly. ------------ #### Constraints **This problem uses bundled tests.** For $100\%$ of the data, it is guaranteed that $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 by ChatGPT 5