#P17704. [2026年江苏省队集训]树

[2026年江苏省队集训]树

题目描述

给定一棵 nn 个点的树,点的编号从 11 到 nn。每个点有一个点权,第 ii 个点的点权为 aia_i。

你需要删去这棵树的若干条边,从而形成若干个连通块。每个连通块的价值为其点权之和的平方。

对于所有 k=1,2,⋯ ,nk=1,2,\cdots,n,求把树分为 kk 个连通块时每个连通块价值之和的最小值。

输入格式

本题有多组测试数据。 输入的第一行包含一个整数 TT 表示测试数据组数。

对于每组测试数据:

  • 第一行一个正整数 nn;
  • 第二行 nn 个整数,表示 a1,⋯ ,ana_1,\cdots,a_n;
  • 接下来 n−1n-1 行,每行两个正整数 x,yx,y,表示 xx 号点和 yy 号点之间有一条边。

输出格式

对于每组数据,输出一行,包含 nn 个整数,其中第 ii 个表示 k=ik=i 时的答案。

样例输入

2
7
3 2 1 3 4 1 2
1 2
2 3
2 4
1 5
1 6
3 7
4
1 1 1 1
1 2
2 3
3 4

样例输出

256 128 96 66 54 48 44
16 8 6 4

数据范围

对于所有数据,1≤T≤101\le T\le 10,1≤n≤3001\le n\le 300,1≤ai≤1061\le a_i\le 10^6。

测试点编号 n≤n\le A≤A\le 特殊性质
1,21,2 2020 10610^6 无
3,43,4 300300 1010 保证第 ii 条边连接 ii 和 i+1i+1
5,65,6 5050 无
7∼107\sim 10 300300 10610^6

保证每个 aia_i 均是在 [1,A][1,A] 中均匀随机生成。若无其余规定,则输入中的树是在 nn−2n^{n-2} 种有标号无根树中均匀随机生成。