<题目链接>
题目大意：
给定一颗树，求出树的直径。
解题分析：
树的直径模板题，以下程序分别用树形DP和两次BFS来求解。
树形DP:
#include <cstdio>
#include <algorithm>
using namespace std; const int N = 1e5+;
struct Edge{
int to,val,nxt;
Edge(int _to=,int _val=,int _nxt=):to(_to),val(_val),nxt(_nxt){}
}e[N<<];
int n,m,cnt,ans;
int dp1[N],dp2[N],head[N];
//dp1[u]维护以u为根的子树最长链的长度
//dp2[u]维护以u为根的子树次长链的长度，并且最长链与次长链不重合
inline void add(int u,int v,int w){
e[++cnt]=Edge(v,w,head[u]);
head[u]=cnt;
}
void dfs(int u,int fa){
for(int i=head[u];i;i=e[i].nxt){
int v=e[i].to,cost=e[i].val;
if(v==fa)continue;
dfs(v,u);
if(dp1[v]+cost>dp1[u])dp2[u]=dp1[u],dp1[u]=dp1[v]+cost;
else if(dp1[v]+cost>dp2[u])dp2[u]=dp1[v]+cost;
}
ans=max(ans,dp1[u]+dp2[u]);
}
int main(){
scanf("%d%d",&n,&m);
for(int i=;i<=m;i++){
int u,v,c;char ch;scanf("%d%d%d %c",&u,&v,&c,&ch);
add(u,v,c);add(v,u,c);
}
dfs(,-);
printf("%d\n",ans);
}
BFS
#include <cstdio>
#include <queue>
#include <cstring>
#include <algorithm>
using namespace std; const int N = 1e5+;
int n,m,cnt,ans,res; struct Edge{
int to,val,nxt;
Edge(int _to=,int _val=,int _nxt=):to(_to),val(_val),nxt(_nxt){}
}edge[N<<];
int head[N],d[N],vis[N]; inline void add(int u,int v,int w){
edge[++cnt]=Edge(v,w,head[u]);head[u]=cnt;
}
void bfs(int s){
memset(vis,,sizeof(vis));
queue<int>que;
vis[s]=;d[s]=;
que.push(s);
while(!que.empty()){
int u=que.front();
que.pop();
for(int i=head[u]; i; i=edge[i].nxt){
int v=edge[i].to;
if(!vis[v]){
d[v]=d[u]+edge[i].val;
vis[v]=;
que.push(v);
if(d[v]>ans) //更新最远距离
ans=d[v],res=v;
}
}
}
}
int main(){
scanf("%d%d",&n,&m);
for(int i=;i<=m;i++){
int u,v,w;char ch;scanf("%d%d%d %c",&u,&v,&w,&ch);
add(u,v,w);add(v,u,w);
}
bfs();bfs(res); //两遍BFS，第一遍求出直径上的一个端点，第二遍求出另一个端点
printf("%d\n",ans);
}