题意：
n个点，m条边，m <= n <= 100000，边的长度都为1。
点从 0 ~ n-1 编号。开始时图是不连通的，并且没有环。
通过加入一些边后，可以使图连通。要求加入的边不能多余（即生成的图是一棵树）。
问连通后的图，任意两点之间的距离的最大值，最小可以是多少？
既然刚开始图不连通也无环，那么就是一些树（特殊情况是点）。
于是题目就变成了，如何把很多棵树连起来，使最后生成的树直径最小。
可以想到，如果把两棵直径为 a 和 b 的树加一条边连成一棵，那么直径最小的新树直径为 (a+1)/2 + (b+1)/2 + 1 （两棵树的直径 / 2，向上取整，的和再加 1）
选择其中一个直径最大的子树，遍历所有其他的子树，然后将其他的子树加到这个子树上面。
求树的直径可以用DP。
这道题场上很快想出来了做法。然后一直T在 test 22。
原因是不会写树的直径DP求法，以及，memset超时。
每次找到新的联通块（新的一棵树）求树的直径就要memset一遍是不需要的。因为那些点肯定是不冲突的。
#include <cstdio>#include <cstring>#include <algorithm>#include <iostream>#include <queue>#include <cmath>#include <stack>#include <set>#include <map>using namespace std;const int maxn = 200000 + 1000;int fa[maxn], dis[maxn], tot = 0, v[maxn];bool vis[maxn];struct Node{ ???int v, next, last, z;}a[maxn];void build(int x, int y){ ???tot++; ???a[tot].v = y; ???a[tot].next = a[x].last; ???a[x].last = tot;}void dp(int x, int &ans){ ???v[x] = 1; ???for (int tmp = a[x].last; tmp; tmp = a[tmp].next) ???{ ???????int y = a[tmp].v; ???????if (v[y]) continue; ???????dp(y, ans); ???????ans = max(ans, dis[x] + dis[y] + 1); ???????dis[x] = max(dis[x], dis[y] + 1); ???}}void DFS(int x){ ???vis[x] = true; ???for (int tmp = a[x].last; tmp; tmp = a[tmp].next) ???{ ???????int y = a[tmp].v; ???????if (!vis[y]) DFS(y); ???}}int main(){ ???int n, m; ???scanf("%d%d", &n, &m); ???int x, y; ???for (int i = 1; i <= m; i++) ???{ ???????scanf("%d%d", &x, &y); ???????build(x, y); ???????build(y, x); ???} ???memset(vis, false, sizeof(vis)); ???????memset(v, 0, sizeof(v)); ???memset(dis, 0, sizeof(dis)); ???int q[maxn], tt = 0; ???for (int i = 0; i < n; i++) ???????if (!vis[i]) ???????{ ???????????int t = 0; ???????????dp(i, t); ???????????q[++tt] = t; ???????????DFS(i); ???????} ???int ans = 0, flag = 0; ???for (int i = 1; i <= tt; i++) ???????if (q[i] > ans) ???????{ ???????????ans = q[i]; ???????????flag = i; ???????} ???for (int i = 1; i <= tt; i++) ???????if (i != flag) ???????????ans = max(ans, (q[i]+1)/2+(ans+1)/2 + 1); ???printf("%d\n", ans);return 0;}Gym - 100781A Adjoin the Networks （树的直径）
原文地址：https://www.cnblogs.com/ruthank/p/9379848.html