http://www.tsinsen.com/

清橙网格自动评测系统

>> 用户名或邮箱:   密码:       忘记密码   其他登录:
 
 
 
A1316. 城市改建(沈添笑)
时间限制:1.5s   内存限制:256.0MB   Special Judge
总提交次数:   AC次数:   平均分:
将本题分享到:
   
 
问题描述
  cs城由n座美丽的小镇组成,小镇之间通过n-1条公路连接,任意两个小镇都能互达。尽管如此,居民还是会向他们的负责人yy抱怨:两座小镇之间的距离(经过的公路数)太远了!yy体恤民情,打算重建城市。yy认为,n-1条公路足矣,丝毫没有浪费,他决定依旧保持这个结构。并且,yy并不打算大兴土木,因此他只会拆除一条公路再新建一条公路。
  作为yy的助理,你需要帮他计算出重建城市后最远的两座小镇距离最近是多少(若存在两个小镇不能互达,则距离为无穷远),并给出任意一组合法方案。
输入格式
  输入的第一行包含一个整数n。接下来n-1行,每行两个整数a、b,代表一条公路。
输出格式
  输出3行。第一行包含一个整数,表示重建后最远的两座小镇的最近距离。第二行包含两个整数,代表拆除的公路。第三行包含两个整数,代表新建的公路。
样例输入
4
1 2
2 3
3 4
样例输出
2
3 4
4 2
数据规模和约定
  20%的数据满足:n≤30
  60%的数据满足:n≤3000
  100%的数据满足:1≤n≤300000、1≤a、b≤n 保证输入数据合法
Note:如果输出第一行正确,后两行有误或缺失,你可以得到该测试点40%的分数