http://tioj.redirectme.net:8080/JudgeOnline/showproblem?problem_id=1213

先隨便戳一個點(第一個)

找出離他最遠的點

再從那個點再做一次DFS

P.S. 這題是多測資…害我WA了好幾次= =

#include <stdio.h>  
#include <string.h>  
#include <vector>  
#include <algorithm>  
using namespace std;  

typedef struct {  
 int to, cost;  
} edge;  
vector<edge> G[100001];  
int max_v, max_d;  
bool used[100001] = {false};  
void dfs(int v, int d)  
{  
 used[v] = true;  
 if (d > max_d) {  
 max_v = v;  
 max_d = d;  
 }  
 for (int i = 0; i < G[v].size(); i++) {  
 edge e = G[v][i];  
 if (!used[e.to]) {  
 dfs(e.to, d + e.cost);  
 }  
 }  
 return ;  
}  
int main()  
{  
 int n;  
 while (scanf("%d", &n) != EOF && n) {  
 for (int i = 0; i <= n; i++) {  
 G[i].clear();  
 }  
 for (int i = 0; i < n - 1; i++) {  
 int s, t;  
 edge e;  
 scanf("%d%d%d", &s, &t, &(e.cost));  
 e.to = t;  
 G[s].push_back(e);  
 e.to = s;  
 G[t].push_back(e);  
 }  
 memset(used, false, sizeof(used));  
 max_d = 0;  
 max_v = 1;  
 dfs(1, 0);  
 memset(used, false, sizeof(used));  
 max_d = 0;  
 dfs(max_v, 0);  
 printf("%d\n", max_d);  
 }  
 return 0;  
}