#P9096. [PA2020] Sen o podboju
[PA2020] Sen o podboju
题目描述
题目译自 PA 2020 Runda 2 Sen o podboju
国王 Byteur,Byteotia 的统治者,目前正梦想着征服 Bitotia。就像在现实世界中一样,在他的梦中他还远远没有打败敌人。因此,他想知道他能做些什么来削弱敌国的实力……
在他的梦中,Bitotia 由 个城市(编号从 到 )组成,由 条双向道路连接,可以只用这些道路从任意一个城市到达任意其他城市。换句话说,Bitotia 的地图形成了一棵树。然而,Byteur 并不记得 Bitotia 的确切道路网络……所以他的脑内生成了一个随机的道路网络。
国王得出的结论是,强行将 Bitotia 分割成 个小国是个好主意。Byteur 所说的划分,是指秘密地破坏正好是 条道路,这将迫使 Bitotia 分解成 个小国,这些小国是去除选定的边后形成的连通子图。
然而,对于国王来说,摧毁任何 条道路都是不够的。每个 Bitotia 的城市都有一个军事系数 ,也是由 Byteur 脑内想出来的。Byteur 知道,一个小国的军事力量越强,对 Byteotia 的威胁就越大。更准确地说:如果在一个小国,其城市的军事系数之和等于 ,那么来自这个小国的威胁就等于 。对 Byteotia 的总威胁等于这 个小国所产生的威胁之和。
现在 Byteur 求助于你——他的梦想(指的是字面意思!)程序员。请帮助他,计算出 Bitotia 分裂成各州后可能产生的最小总威胁。由于 Byteur 还没有决定参数 的值,请计算 取从 到 (包含两端)所有值的结果。
输入格式
第一行包含一个整数 ,表示测试点总数 Byteur 做的梦的个数。接下来描述每一组测试点,测试点的输入格式都相同。
每个测试点第一行包含一个整数 。
第二行包含一个长度为 的整数序列 。
接下来 行是 Bitotia 的路网描述,每行两个整数 ,表示城市 被一条路相连。保证输入的图是一棵树。
Byteur 按如下方法生成数据。首先手动选取一个整数 ,一个整数区间 和 的值。接下来按如下步骤独立生成每个测试点:
- 城市个数 的值从 区间内均匀随机选取。
- 每个 的值从 区间内独立均匀随机选取。
- 生成一个自然数序列 。序列中的每一个元素都是从 区间中独立均匀随机选取的。Byteur 将其作为路网的 Prüfer 序列,也就是测试点中给出的树的 Prüfer 序列是 。
输出格式
输出 行,描述每个测试点的答案。每行包含 个整数(其中 是输入中的城市数量);第 个整数表示 Bitotia 在被划分为 个小国后所能造成的最小威胁。
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
提示
样例 1 解释
以上测试数据使用随机数种子为 , 的参数生成。
对于第一个测试案例,输出的第一个数字是 ,代表未被分割的 Bitotia 所带来的总威胁。输出的第二个数字对应的是如果连接 号和 号城市的道路被摧毁的总威胁;在这种情况下,威胁将是 。
数据生成
本题的样例生成器在附件中给出。生成器将以下内容作为输入接受:生成器种子和数字 。本题的所有测试数据都将用与之相当的生成器生成(即用不同的伪随机数库,与编译器的实现无关)。
为了确保测试的随机性,每个测试点的 的值都是手动选择的,生成器的种子是随机选择的。
数据范围
本题采用捆绑测试
对于 的数据,保证 ,,,,,。