3143: 地铁规划

N 市现有的城市骨干铁路系统是一棵（数据结构意义下的）树，树的顶点为重要交通节 点，树的边为现有的铁轨设施。 现在你需要帮忙，在这一铁路系统树之上规划 N 市新的地铁线路系列。N 市的地铁列车只 会从一条线路的一头往返于另一头，因此线路上没有分叉。开发更多的地铁线路会大幅增加乘 客复杂度和费用成本，相比之下线路的长度无关紧要。为了简化问题，线路可以只有一个站。 可以给出一个形式化的定义——定义链为：由 X 个点和 X-1 条边组成的连通块，其中 X≥ 1，每个点的度数≤2。我们称，N 市的地铁线路只能是由若干条链形成的。 为了线路清晰，乘客方便，同时成本最低，N 市的城市规划局希望你能给出一种建设方 案，使得

1)地铁线路能够覆盖 N 市骨干系统的所有节点，

2)没有一个节点同时被两条或以上 线路覆盖，同时

3)所有地铁线路只利用铁路系统上现有的铁轨完成。 你需要告诉他们，最少能够建设几条地铁线路，来满足这一需求。

第一行有有个数 N，表示城市骨干铁路系统树的节点的个数。 第二行到第 N 行，每行两个数 X、Y，表示在树上点 X 与 Y 之间有边相连。

一行，包含一个数，表示最少的铁路线路数。

4
1 2
1 3
1 4

2