#6047. [提高组模拟试题]网络连接

内存限制:512 MiB 时间限制:2000 ms 输入文件:network.in 输出文件:network.out
题目类型:传统 评测方式:文本比较
上传者: zhouhao

题目描述

Yazid 所在的 Duck 公司最近面临了一个棘手的网络连接问题。 Duck 公司共有 n 台电脑,电脑之间可以通过网线相连。网络管理员 Yazid 使用了n − 1 根网线连接这些电脑,其中每跟网线都连接了两台电脑。所有的电脑都由这些网线直接或间接互联,根据常识,n − 1 也是最少的需要使用的网线数目。 近期,由于公司拓展业务,部分电脑需要被分离出原网络,建立起新的局域网。具 体来说,每台电脑均有恰好 50% 的概率被分配于新任务,否则即执行旧任务。所有电脑被分配新、旧业务的概率是相互独立的。 在分配任务后,对于任意网线,如果它连接的两台电脑执行的任务不同,Duck 公司就将会将它们切断。而 Yazid 的任务,即是使用一些新的网线,将执. 行. 同. 一. 任. 务. 的电脑全部互联。 虽然 Duck 公司有足够的新网线,但事实上,最棘手的问题在于紧缺的网口。被切断网线所占据的网口已不能再用,而每台电脑恰好有 1 个额外的网口可用于接入网线, 每需增加 1 个网口,Yazid 就需要支付 1 个金币。这也就意味着,如果 Yazid 希望在同一台电脑上新连接超过 1 根网线,他就需要支付额外的费用。 Yazid 聪明绝顶,一旦任务分配确定,他就一定会花费最少的金币完成目标。而 Duck 公司对 Yazid 的期望花费非常感兴趣,并希望你帮他们计算该期望值。 而聪明的你应该早已发现,这个期望值与 2n 的乘积一定是一个整数,因此你只打算告诉 Duck 公司该期望值与 2n 的乘积对 998, 244, 353 取模的结果。

输入格式

从文件 network.in 中读入数据。 本题包含多组数据,第一行一个非负整数 T ,表示数据组数。接下来依次描述每组数据,对于每组数据: • 第一行一个正整数 n,表示 Duck 公司的电脑数目。 • 接下来 n − 1 行描述所有初始的网线,每行 2 个用单个空格隔开的正整数 u, v 描述一根连接电脑 u, v 的网线。 – 电脑的编号从 1 开始。 – 保证 1 ≤ u, v ≤ n。 – 保证所有电脑被这些网线连通。

输出格式

输出到文件 network.out 中。 对于每组数据: • 输出一行一个整数,表示期望花费金币数与 2n 的乘积对 998, 244, 353 取模的结果。

样例

【样例 1 输入】

2 2
1 2 4
1 2
3 1
4 1

【样例 1 输出】

0 2

【样例 1 解释】

对于第一组数据,无论任务如何分配,都一定不需要新的网线了。
对于第二组数据, 只有 2, 3, 4 号电脑被分配的任务相同, 且与 1 号电脑被分配的任务不同时, 才会需要额外的 1 个网口, 其发生的概率为 1/8 , 因此答案为1/8× 2^4 mod 998, 244, 353 = 2。

【样例 2 输入】

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

【样例 2 输出】

24

【样例 2 解释】

下图是一个例子:如果只有 2 号电脑被分配于新任务,那么聪明绝顶的 Yazid 可以按如下方法做连接(蓝、黄网口分别表示免费、付费网口),使其只需花费 1 个金币。(图见PDF)

【样例 3】

见选手目录下的 network/network3.in 与 network/network3.out。

【子任务】

详见PDF

数据范围与提示

对于所有测试点,保证 T ≤ 3。 对于所有测试点中的所有数据,保证 n ≤ 2000。