树的直径即树中最长的路径的长度。
用两次dfs，第一次从任意点出发求得一个最远点p，
第二次从p出发求得最远点，这条路径就是最长路，即所求。
#include #include #include #include #include #include #include #include #include #define inf 0x3f3f3f3f #define eps 1e-6 #define ll __int64 using namespace std; struct node { int v,w,next; }e[80010]; int n,m,ans,p,h,head[40010],vis[40010]; void addedge(int a,int b ,int c) { e[h].v=b; e[h].w=c; e[h].next=head[a]; head[a]=h++; } void init() { memset(head,-1,sizeof head); h=0; } void dfs(int x,int num) { vis[x]=1; if(num>ans) ans=num,p=x; for(int i=head[x];i!=-1;i=e[i].next) { if(!vis[e[i].v]) dfs(e[i].v,num+e[i].w); } } int main() { int a,b,c; char s[10]; while(~scanf("%d%d",&n,&m)) { init(); while(m--) { scanf("%d%d%d%s",&a,&b,&c,s); addedge(a,b,c); addedge(b,a,c); } ans=0; memset(vis,0,sizeof vis); dfs(1,0); memset(vis,0,sizeof vis); dfs(p,0); printf("%d\n",ans); } return 0; }