题目传送：UVA – 10308
思路：就是树的遍历，DFS即可，注意输入
AC代码：
#include <cstdio>#include <cstring>#include <iostream>#include <string>#include <sstream>#include <algorithm>#include <cmath>#include <queue>#include <stack>#include <vector>#include <map>#include <set>#include <deque>#include <cctype>#define LL long long#define INF 0x7fffffffusing namespace std;struct node {int e, w;node(int _e, int _w) : e(_e), w(_w) { }}; const int maxn = 10010;vector<node> G[maxn];int ans;int dfs(int u, int fa) {int maxx = 0;//maxx表示当前结点到叶子结点的最大权值int anss;//anss表示当前结点到叶子结点的权值 int len = G[u].size();for(int i = 0; i < len; i ++) {if(G[u][i].e != fa) {anss = dfs(G[u][i].e, u) + G[u][i].w;ans = max(ans, anss + maxx);//更新答案maxx = max(anss, maxx);//更新最大权值 }}return maxx;}int main() {string s;while (!cin.eof()) {for(int i = 0; i < maxn; i ++)G[i].clear();getline(cin, s);while (s.length() > 0 && !cin.eof()){stringstream ss;ss << s;int u, v, w;ss >> u >> v >> w;G[u].push_back(node(v, w));G[v].push_back(node(u, w));getline(cin, s);}ans = 0;dfs(1, -1);printf("%d\n", ans);}return 0;}
，怠惰是贫穷的制造厂。
