中文题面，给出一个图，问能不能成环，如果可以就输出YES。否则输出该树的直径。
这里的判环我们用路径压缩的并查集就能很快的判断出来，可以在输入的同时进行判断。这题重点就是求树的直径。
树直径的性质可以参考https://blog.csdn.net/pi9nc/article/details/12394117 实现在代码求法上的就是：
假设 s-t这条路径为树的直径，或者称为树上的最长路
从任意一点u出发搜到的最远的点一定是s、t中的一点，然后在从这个最远点开始搜，就可以搜到另一个最长路的端点，即用两遍广搜就可以找出树的最长路
搜的时候要注意 ，什么时候该清空什么数组 在代码中有一定的解释
#include<iostream>
#include<vector>
#include<queue>
#include<string.h>
using namespace std;
#define p pair<int,int>
vector<p> a[];
bool pd[],pdd[]; //pd数组判断该点有没有遍历到 pdd数组是保证每一个点都要被遍历过
int dp[]; //dp值为以改点为起点最长路径，在第一次找端点遍历后要清零
int ans,mark,anss;//annss为最终答案，mark用来标记第一次bfs找到的树的直径的端点
int bfs(int u)
{
ans=;
memset(pd,false,sizeof(pd));
memset(dp,false,sizeof(dp));
pd[u]=pdd[u]=;
queue<int> q;
q.push(u);
while(q.size()!=)
{
int t=q.front();
q.pop();
for(int i=;i<a[t].size();i++)
{
int v=a[t][i].first;
if(pd[v]) continue;
int w=a[t][i].second;
//cout<<"w="<<w<<endl; pd[v]=pdd[v]=;
dp[v]=dp[t]+w;
if(ans<dp[v])
{
ans=dp[v];
mark=v;
}
q.push(v);
}
}
return mark;
}
int f[];//压缩路径并查集
int die(int u)
{
if(f[u]==u) return u;
f[u]=die(f[u]);
return f[u];
}
int main()
{
int i,j,k,l,x,y,n,huan,m;
while(scanf("%d%d",&n,&m)!=EOF)
{
memset(pdd,false,sizeof(pdd));
huan=;anss=;
int u,v,c;
for(i=;i<=n;i++) f[i]=i,a[i].clear();//初始化father数组，同时清空上个输入留下的关系路径
for(i=;i<=m;i++)
{
scanf("%d%d%d",&u,&v,&c);
x=die(u);y=die(v);
if(x!=y) f[x]=y;
else huan=; //代表能成环
a[u].push_back(p(v,c));
a[v].push_back(p(u,c));
}
if(huan)
{
printf("YES\n");
continue;
}
for(i=;i<=n;i++) //循环保证所有的点都被遍历过
{
if(!pdd[i])
{
int sb=bfs(i);
// cout<<ans<<endl;
// cout<<"sb="<<sb<<endl;
int hp=bfs(sb);
// cout<<ans<<endl;
anss=max(anss,dp[hp]);
}
} printf("%d\n",anss); } }