总的来说，如果直径只看边权的话，(Dfs)和(DP)要区分开来，(Dfs)不能处理负边权，而(DP)可以。
如果包含点权的话，建议(Dfs),可以方便的记录路径。
例题：(APIO2010)巡逻
很水，找两遍直径即可。
#include<bits/stdc++.h>
using namespace std;
inline int read()
{
int f=1,w=0;char x=0;
while(x<'0'||x>'9') {if(x=='-') f=-1; x=getchar();}
while(x!=EOF&&x>='0'&&x<='9') {w=(w<<3)+(w<<1)+(x^48);x=getchar();}
return w*f;
}
const int N=200100;
map<int,int> PL;
int n,K,num_edge;
int head[N],fa[N],L[3],las[N],d[N];
struct Edge {int next,to,dis;} edge[N];
inline void Add(int from,int to,int dis)
{
edge[++num_edge].next=head[from];
edge[num_edge].dis=dis;
edge[num_edge].to=to;
head[from]=num_edge;
}
inline void dfs(int pos,int fa,int from)
{
las[pos]=from;
for(int i=head[pos];i!=-1;i=edge[i].next)
if(edge[i].to!=fa&&!d[edge[i].to])
{
d[edge[i].to]=edge[i].dis+d[pos];
dfs(edge[i].to,pos,i);
}
}
inline void Find_Dia(int from)
{
memset(d,0,sizeof(d));
dfs(from,0,0);
for(int i=1;i<=n;i++) if(d[i]>d[from]) from=i;
memset(d,0,sizeof(d));memset(las,-1,sizeof(las));
dfs(from,0,-1);int end=from;
for(int i=1;i<=n;i++) if(d[i]>d[end]) end=i;L[1]+=d[end];
while(las[end]!=-1)
edge[las[end]].dis=-1,
edge[las[end]^1].dis=-1,
end=edge[las[end]^1].to;
}
inline void Find_DP(int pos,int fa)
{
for(int i=head[pos];i!=-1;i=edge[i].next)
if(edge[i].to!=fa)
{
Find_DP(edge[i].to,pos);
L[2]=max(L[2],d[pos]+d[edge[i].to]+edge[i].dis);
d[pos]=max(d[pos],d[edge[i].to]+edge[i].dis);
}
}
int main(){
#ifndef ONLINE_JUDGE
//freopen("A.in","r",stdin);//Ans=11;
//freopen("B.in","r",stdin);//Ans=10;
freopen("C.in","r",stdin);//Ans=6;
#endif
n=read();K=read();
memset(head,-1,sizeof(head));num_edge=-1;
for(int i=1,u,v;i<n;i++)
u=read(),v=read(),Add(u,v,1),Add(v,u,1);
if(K==1) {Find_Dia(1),printf("%d",2*n-L[1]-1);return 0;}
Find_Dia(1);memset(d,0,sizeof(d));
Find_DP(1,0);
printf("%d
",2*n-L[1]-L[2]);
/*printf("%d %d
",L[1],L[2]);
for(int i=1;i<=2*(n-1);i++)
{
printf("to:%d,dis:%d
",edge[i].to,edge[i].dis);
}*/
}