/ Vijos / 题库 /

旅游规划(csapc)

旅游规划(csapc)

描述

W市的交通规划出现了重大问题,市政府下决心在全市的各大交通路口安排交通疏导员来疏导密集的车流。但由于人员不足,W市市长决定只在最需要安排人员的路口安放人员。具体说来,W市的交通网络十分简单,它包括n个交叉路口和n-1条街道,任意一条街道连接两个交叉路口,并且任意两个交叉路口之间都存在一条路径互相连接。经过长期调查结果显示如果一个交叉路口位于W市交通网的最长路径上,那么这个路口必然拥挤不堪,所谓最长路径定义为某条路径p=(v1,v2,v3…vk),路径经过的路口各不相同且城市中不存在长度>k的路径(因此可能存在着不唯一的最长路径)。因此W市市长希望知道有哪些路口位于城市交通网的最长路径之上。

格式

输入格式

第一行包括一个整数n。

之后的n-1行每行包括两个整数u, v表示编号为u和v的路口之间存在着一条街道(注意:路口被依次编号为0到n-1)

输出格式

输出包括若干行,每行包括一个整数——某个位于最长路上路口的编号。

为了确保解唯一,我们规定位于所有最长路上的路口按编号顺序从小到大输出。

样例1

样例输入1

10
0 1
0 2
0 4
0 6
0 7
1 3
2 5
4 8
6 9

样例输出1

0
1
2
3
4
5
6
8
9

提示

这里存在着若干条最长路径,其中的两条是3-1-0-2-5与8-4-0-6-9,他们的长度都是5,但是不存在长度>5的路径且所有最长路径都不包括路口7,所以答案中没有7。

数据范围:
对于50%的数据保证n<=1000
对于100%的数据保证n<=200000

信息

ID
1476
难度
7
分类
动态规划 | 树形DP 点击显示
标签
递交数
585
已通过
129
通过率
22%
上传者

相关

在下列训练计划中:

RP++分类题库

在下列比赛中:

第一届海峡两岸青少年程序设计竞赛