#P17704. [2026年江苏省队集训]树
[2026年江苏省队集训]树
题目描述
给定一棵 个点的树,点的编号从 到 。每个点有一个点权,第 个点的点权为 。
你需要删去这棵树的若干条边,从而形成若干个连通块。每个连通块的价值为其点权之和的平方。
对于所有 ,求把树分为 个连通块时每个连通块价值之和的最小值。
输入格式
本题有多组测试数据。 输入的第一行包含一个整数 表示测试数据组数。
对于每组测试数据:
- 第一行一个正整数 ;
- 第二行 个整数,表示 ;
- 接下来 行,每行两个正整数 ,表示 号点和 号点之间有一条边。
输出格式
对于每组数据,输出一行,包含 个整数,其中第 个表示 时的答案。
样例输入
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
数据范围
对于所有数据,,,。
| 测试点编号 | 特殊性质 | ||
|---|---|---|---|
| 无 | |||
| 保证第 条边连接 和 | |||
| 无 | |||
保证每个 均是在 中均匀随机生成。若无其余规定,则输入中的树是在 种有标号无根树中均匀随机生成。