第十三届安徽省大学生程序设计大赛_K基地安全(树形DP)
2022-06-21 05:06 作者:Clayton_Zhou | 我要投稿
题目描述:
网络安全一直是非常重要的一件事情，现在太空观测基地里的机房所有主机都用网线相连，如图所示，主机编号为1..N。在这个环内有一些额外的网线直接连接两台主机。为了机房网线布线合理，任意两条网线中途不能相交。为了使主机之间的网络更加通畅，主机之间会尽可能的相连，但两台主机之间最多连接一条网线。
现在想测试这个机房网络系统的安全性能，需要在一些主机上安装监测软件，使每条网线都能被检测（在第i号主机安装监测软件可以监测与它直接相连的网线）。请问最少需要在多少台主机上安装监测软件。
输入说明:
第一行有一个正整数N（N<=100000），表示主机数。接下来2*N-3行（环上有N台主机，环内有N-3条网线），每行两个正整数u、v，表示主机u与主机v之间有一条网线。
输出说明:
一个正整数，表示最少的安装监测软件的主机数目。
输入样例:
8
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 1
1 3
8 3
7 3
7 5
5 3
输出样例:
4
