树的直径类模板题。
题目大意
给你一个森林，你可以连若干条边，但是连边之后整个图仍然是一个森林。问你连完后的最大直径。
题目中的“直径”意思是连接的点的个数。
解题思路
为了使得能连接的点的个数最多，我们肯定要把每棵树的直径连在一起，这样就能使得答案最大。
所以，我们只需要对于每棵树求一遍直径，然后把答案累加起来就能够 AC 了。
树的直径还是简单提以下吧。可以使用树形 DP 求解。我们设 \(dp_{i,0}\) 为从 \(i\) 号点出发的最长链，\(dp_{i,1}\) 表示次长链（但是与最长链没有重复部分）。如果 \(dp_{son,0}+1>dp_{i,0}\)，那么就能够更新最长链，把次长链更新成原来的最长链即可。如果 \(dp_{son,0}+1>dp_{i,1}\)，就直接更新次长链。
AC 代码：
#include <iostream>
#include <vector>
#define int long long
using namespace std;bool vis[100005];
vector<int> g[100005];
int dp[100005][2];
int n,m;
int nowans = 0;
void dfs(int now,int fa){vis[now] = true;dp[now][0] = dp[now][1] = 1;for(auto it:g[now]){if(it==fa) continue;dfs(it,now);if(dp[it][0]+1>dp[now][0]){dp[now][1] = dp[now][0];dp[now][0] = dp[it][0]+1;}else if(dp[it][0]+1>dp[now][1]){dp[now][1] = dp[it][0]+1;}}nowans = max(nowans,dp[now][0]+dp[now][1]-1);
}
signed main()
{ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);cin>>n>>m;for(int i = 1;i<=m;i++){int u,v;cin>>u>>v;g[u].push_back(v);g[v].push_back(u);}int fans = 0;for(int i = 1;i<=n;i++){if(!vis[i]){//计算每棵树的直径，加和dfs(i,-114514);fans+=nowans;nowans = 0;}}cout<<fans;return 0;
}