P6431 [COCI 2008/2009 #1] KRTICA

有一棵 $n$ 个点的树，边权都为 $1$。 现在想删去一条边，增加一条边，使得最远的两个点距离最短。

第一行为一个整数 $n$。 接下来 $n-1$ 行，每行两个整数 $a$ 和 $b$，表示有树上有一条从 $a$ 到 $b$ 的无向边。

**本题存在 SPJ**。 第一行只有一个整数，表示删去一条边，增加一条边后最远的两个点的距离。 第二行两个整数，表示被删掉的一条边。 第三行两个整数，表示被增加的一条边。

#### 数据规模与约定 - 对于 $40\%$ 的数据，保证 $n\le 30$。 - 对于 $70\%$ 的数据，保证 $n\le 3\times 10^3$。 - 对于 $100\%$ 的数据，保证 $1\le n \le 3\times 10^5$，$1\le a,b\le n$。 --- #### 计分标准 - 如果输出的第一行不正确，得 $0$ 分。 - 如果输出得第一行正确，但是剩下的数字不正确或数量不足四个，得对应测试点 $70\%$ 的分数。 - 如果输出第一行正确，且给出的方案是可行且正确的，得到对应测试点 $100\%$ 的分数。 --- #### 说明 本题译自 [Croatian Open Competition in Informatics 2008/2009](https://hsin.hr/coci/archive/2008_2009) [Contest #1](https://hsin.hr/coci/archive/2008_2009/contest1_tasks.pdf) T6 KRTICA。 SPJ provided by @Tweetuzki