Description
小D最近又在种树，可是他的种树技巧还是很差，种出的树都长的歪七扭八，为了让树变得平衡一些，小D决定从树上删掉一条边，然后再加上一条边，使得到的仍然是一棵树并且这棵树的直径（树上最远两点距离）尽量小。请你求出新树的最小直径长度。每条边的长度均为1。
Input Format
第一行一个正整数n，表示树上节点个数。第2~n行每行两个正整数x,y，表示x到y之间有一条边。
Output Format
输出一个整数，表示答案。
Solution
我们发现，删除的那条边一定是在原先直径上，
然后可以证明，接的边接到原树的中心（即直径的中点），会使新直径最小，
只要证明出这个，就可以枚举直径每条边，
而删除一条边后树被分成两半，那么新树的直径有3种情况，
要么是两部分各自的直径，或者直径穿过新接的边，取最大值更新Ans即可，
求直径可以用2遍DFS求得，
Code
#include#include #include #define LL long long#define N 500010using namespace std;struct info { int to, nex;} e[N * 2];int n, m, tot, head[N * 2], Ans;int ds, dt, tmp, dis[N], F1[N], F2[N];inline int read() { int x = 0, f = 1; char ch = getchar(); while (ch < '0' || ch > '9') {if (ch == '-')f = -1; ch = getchar();} while (ch >= '0' && ch <= '9') {x = x * 10 + ch - '0'; ch = getchar();} return x * f;}inline void add_edge(int u, int v) { e[++tot].to = v; e[tot].nex = head[u]; head[u] = tot;}void FD(int u, int fa) { if (dis[u] > dis[tmp]) tmp = u; for (int i = head[u]; i; i = e[i].nex) { int v = e[i].to; if (v == fa) continue; dis[v] = dis[u] + 1; FD(v, u); }}void dfs(int u, int fa) { dis[u] = 0; for (int i = head[u]; i; i = e[i].nex) { int v = e[i].to; if (v == fa) continue; dfs(v, u); F1[u] = max(F1[u], max(F1[v], dis[u] + dis[v] + 1)); dis[u] = max(dis[u], dis[v] + 1); }}bool dddfs(int u, int fa) { if (u == dt) return 1; for (int i = head[u]; i; i = e[i].nex) { int v = e[i].to; if (v == fa || !dddfs(v, u)) continue; Ans = min(Ans, max(max(F1[u], F2[v]), ((F2[v] + 1) >> 1) + ((F1[u] + 1) >> 1) + 1)); return 1; } return 0;}int main() { n = read(); bool flag = 1; for (int i = 1; i < n; ++i) { int u = read(), v = read(); if ((u != i + 1 || v != i) && (u != i || v != i + 1)) flag = 0; add_edge(u, v); add_edge(v, u); } if (flag) {printf("%d\n", (n + 1) >> 1); return 0;} FD(1, 0); dis[ds = tmp] = 0; tmp = 0; FD(ds, 0); Ans = dis[dt = tmp]; dfs(ds, 0); memcpy(F2, F1, sizeof(F1)); memset(F1, 0, sizeof(F1)); dfs(dt, 0); dddfs(ds, 0); printf("%d\n", Ans); return 0;}