自动搬运

查看原文

来自洛谷，原作者为

	Naro_Ahgnay 值得就喜欢。

搬运于2025-08-24 22:35:17，当前版本为作者最后更新于2022-01-15 17:12:42，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题目大意

现有一个森林图，随意添加边使它成为一棵树。求这棵树的直径。

思路

树的直径：树上最远两点间的距离。

我们可以把森林中每一棵树的直径两端连接起来。因为一棵树的直径原本就是这棵树中最长的链，所以在新树中也不可能存在比这条新的、用原来的树的直径组成的链更长的新链。那么很明显，答案就是该森林中所有树的直径的和。

那么怎么求出这个距离呢？求树的直径有很多方法，可以使用两遍 dfs 求直径的方法。

step 1

在树上随便选一个点作为起点，然后向它能到达的走去。记录下走过的点数。

step 2

找出从起点开始，步数最多的点，记录下来，作为下一次 dfs 的起点。

step 3

从刚才新的起点开始，继续搜索它能到达的点。最后距离新起点最远的点和新起点的距离就是这棵树的直径。

求出每棵树的直径，然后加起来就成了最终的答案。

code

#include<bits/stdc++.h>
using namespace std;
int n,m,u,v,ans,res,id;
int in[100001];
bool vis[100001];
vector<int> g[100001];
void dfs(int x,int z)
{
	vis[x]=1;
	if(res<z) res=z,id=x;
	int si=g[x].size();
	for(int i=0;i<si;i++)
		if(!vis[g[x][i]]) dfs(g[x][i],z+1);
	return;
}
void sfd(int x,int f,int z)
{
	res=max(res,z);
	int si=g[x].size();
	for(int i=0;i<si;i++)
		if(g[x][i]!=f) sfd(g[x][i],x,z+1);
	return;
}
void wok(int x)
{
	res=0;dfs(x,1);
	res=0;sfd(id,id,1);
	ans+=res;
}
int main()
{
//	freopen("P8028.in","r",stdin);
//	freopen("P8028.out","w",stdout);
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++)
	{
		scanf("%d%d",&u,&v);
		g[u].push_back(v);
		g[v].push_back(u);
		in[u]++,in[v]++;
	}
	for(int i=1;i<=n;i++)
	{
		if(in[i]==1&&!vis[i]) wok(i);
		if(!in[i]) ans++;
	}
	printf("%d",ans);
	return 0;
}