F.A.Qs Home Discuss ProblemSet Status Ranklist Contest 入门OJ LoginRegister 捐赠本站
Problem 4871. -- [Shoi2017]摧毁“树状图”

4871: [Shoi2017]摧毁“树状图”

Time Limit: 25 Sec  Memory Limit: 512 MB
Submit: 323  Solved: 133
[Submit][Status][Discuss]

Description

自从上次神刀手帮助蚯蚓国增添了上千万人口(蚯口?),蚯蚓国发展得越来越繁荣了!最近,他们在地下发现了
一些神奇的纸张,经过仔细研究,居然是D国X市的超级计算机设计图纸!这台计算机叫做‘树状图’,由n个计算
节点与n1条可以双向通信的网线连接而成,所有计算节点用不超过n的正整数编号。顾名思义,这形成了一棵树的
结构。蚯蚓国王已在图纸上掌握了这棵树的完整信息,包括n的值与n1条网线的连接信息。于是蚯蚓国王决定,派
出蚯蚓国最强大的两个黑客,小P和小H,入侵‘‘树状图’’,尽可能地摧毁它。小P和小H精通世界上最好的编程
语言,经过一番商量后,他们决定依次采取如下的步骤:小P选择某个计算节点,作为他入侵的起始点,并在该节
点上添加一个P标记。重复以下操作若干次(可以是0次):–小P从他当前所在的计算节点出发,选择一条没有被
标记过的网线,入侵到该网线的另一端的计算节点,并在路过的网线与目的计算节点上均添加一个P标记。小H选择
某个计算节点,作为她入侵的起始点,并在该节点上添加一个H标记。重复以下操作若干次(可以是0次):–小H
从她当前所在的计算节点出发,选择一条没有被标记过的网线,入侵到该网线的另一端的计算节点,并在路过的网
线与目的计算节点上均添加一个H标记。(注意,小H不能经过带有P标记的网线,但是可以经过带有P标记的计算节
点)删除所有被标记过的计算节点和网线。对于剩下的每条网线,如果其一端或两端的计算节点在上一步被删除了
,则也删除这条网线。经过以上操作后,‘‘树状图’’会被断开,剩下若干个(可能是0个)连通块。为了达到
摧毁的目的,蚯蚓国王希望,连通块的个数越多越好。于是他找到了你,希望你能帮他计算这个最多的个数。小P
和小H非常心急,在你计算方案之前,他们可能就已经算好了最优方案或最优方案的一部分。你能得到一个值x:若
x=0,则说明小P和小H没有算好最优方案,你需要确定他们两个的入侵路线。若x=1,则说明小P已经算好了某种两
人合作的最优方案中,他的入侵路线。他将选择初始点p0,并沿着网线一路入侵到了目标点p1,并且他不会再沿着
网线入侵;你只需要确定小H的入侵路线。若x=2,则说明小P和小H算好了一种两人合作的最优方案,小P从点p0入
侵到了p1并停下,小H从点h0入侵到了h1并停下。此时你不需要指挥他们入侵了,只需要计算最后两步删除计算节
点与网线后,剩下的连通块个数即可。

Input

每个输入文件包含多个输入数据。输入文件的第一行为两个整数 T 和 x, T 表示
该文件包含的输入数据个数, x 的含义见上述。(同一个输入文件的所有数据的 x 都是相同的)
接下来依次输入每个数据。
每个数据的第一行有若干个整数:
 若 x = 0,则该行只有一个整数 n。
 若 x = 1,则该行依次有三个整数 n, p0, p1。
 若 x = 2,则该行依次有五个整数 n, p0, p1, h0, h1。
保证 p0, p1, h0, h1 均为不超过 n 的正整数。
每个数据接下来有 n  1 行,每行有两个不超过 n 的正整数,表示这两个编号的计
算节点之间有一条网线将其相连。保证输入的是一棵树。
同一行相邻的整数之间用恰好一个空格隔开。
对于整数 k,设 ∑ n^k 为某个输入文件中,其 T 个输入数据的 n^k 之和。
所有输入文件满足 T ≤ 10^5, ∑ n^1 ≤ 5 × 10^5。
数据文件可能较大,请避免使用过慢的输入输出方法。

Output

对于每个数据,输出一行,表示在给定条件下,剩下连通块的最大个数。

Sample Input

1 0
13
1 2
2 3
2 4
4 5
4 6
4 7
7 8
7 9
9 10
10 11
10 12
12 13

Sample Output

8
这个输入文件只有一个输入数据。一种最优的方案如下:
小 P 从节点 2 开始入侵,节点 2 被小 P 标记。
小 P 从节点 2 入侵到节点 4,节点 4 和经过的网线被小 P 标记。
小 P 从节点 4 入侵到节点 7,节点 7 和经过的网线被小 P 标记。
小 H 从节点 10 开始入侵,节点 10 被小 H 标记。
删除被标记的节点 2,4,7,10 和被标记的网线 (2,4) 和 (4,7)。
删除任意一端在上一步被删除的网线。
此时还剩下 8 个连通块。其中节点 1,3,5,6,8,9,11 各自形成一个连通块,节点 12,13
形成了一个连通块。

HINT

 2017.4.28新加数据一组By 150137

Source

黑吉辽沪冀晋六省联考

[Submit][Status][Discuss]

HOME Back