| 题目名称 | 1793. [国家集训队2012]城市改建 |
|---|---|
| 输入输出 | nt2012_stx_tree.in/out |
| 难度等级 | ★★☆ |
| 时间限制 | 1500 ms (1.5 s) |
| 内存限制 | 256 MiB |
| 测试数据 | 20 |
| 题目来源 |
 cstdio
于2014-11-03加入 |
| 开放分组 | 全部用户 |
| 提交状态 | |
| 分类标签 | |
| 分享题解 |
| 通过：1， 提交：5， 通过率：20% | ||||
 cstdio |
100 | 2.929 s | 19.77 MiB | C++ |
|
cstdio |
70 | 2.762 s | 19.77 MiB | C++ |
|
cstdio |
50 | 3.067 s | 18.78 MiB | C++ |
 teacher |
0 | 1.983 s | 7.52 MiB | Pascal |
 Wearry |
0 | 4.094 s | 33.24 MiB | C++ |
| 关于 城市改建 的近10条评论(全部评论) | ||||
|---|---|---|---|---|
|
DFS会E掉也是醉了，强行按BFS序来……
树状DP，用一个update(&a,&b,c)更新最大和次大值的想法挺有趣…… | ||||
1793. [国家集训队2012]城市改建
★★☆ 输入文件：nt2012_stx_tree.in
输出文件：nt2012_stx_tree.out
简单对比时间限制：1.5 s 内存限制：256 MiB
城市改建(沈添笑)
时间限制：1.5s 内存限制：256.0MB
【问题描述】
cs城由n座美丽的小镇组成，小镇之间通过n-1条公路连接，任意两个小镇都能互达。尽管如此，居民还是会向他们的负责人yy抱怨：两座小镇之间的距离(经过的公路数)太远了！yy体恤民情，打算重建城市。yy认为，n-1条公路足矣，丝毫没有浪费，他决定依旧保持这个结构。并且，yy并不打算大兴土木，因此他只会拆除一条公路再新建一条公路。
作为yy的助理，你需要帮他计算出重建城市后最远的两座小镇距离最近是多少(若存在两个小镇不能互达，则距离为无穷远)。
作为yy的助理，你需要帮他计算出重建城市后最远的两座小镇距离最近是多少(若存在两个小镇不能互达，则距离为无穷远)。
【输入格式】
输入的第一行包含一个整数n。接下来n-1行，每行两个整数a、b，代表一条公路。
【输出格式】
第一行包含一个整数，表示重建后最远的两座小镇的最近距离。
【样例输入】
4
1 2
2 3
3 4
1 2
2 3
3 4
【样例输出】
2
3 4
4 2
3 4
4 2
【数据规模和约定】
20%的数据满足：n≤30
60%的数据满足：n≤3000
100%的数据满足：1≤n≤300000、1≤a、b≤n 保证输入数据合法
60%的数据满足：n≤3000
100%的数据满足：1≤n≤300000、1≤a、b≤n 保证输入数据合法