UVa 10308 Roads in the North：树上的最长路

UVa 10308 Roads in the North：树上的最长路2014-07-25

10308 - Roads in the North

Time limit: 3.000 seconds

http://uva.onlinejudge.org/index.php？option=com_onlinejudge&Itemid=8&category=115&page=show_problem&problem=1249

思路：由于是一棵树，我们只要随便指定一个树根就开始dfs。所有路径都可以看成以父节点为中转点的“子树甲+子树乙”的形式（只有一个子树的情况也是一样的），遍历时向上返回一个最大的路径长即可。

完整代码：

/*0.016s*/#include<bits/stdc++.h>using namespace std;const int maxn = 10005;char s[30];int ans;vector<pair<int, int> > node[maxn]; /// first: 与node[i]连结的村庄号second: 距离int dfs（int to, int from）{int lto, lans = 0, lmax = 0;for （int i = 0; i < node[to].size（）; ++i）{lto = node[to][i].first;if （lto ！= from）{lans = dfs（lto, to） + node[to][i].second;///递归子树，返回子树中的最长路ans = max（ans, lans + lmax）;///当前得到的子树最长路和前面得到的另一棵子树的最长路之和lmax = max（lmax, lans）;}}return lmax;}int main（）{int u, v, l, i;bool ok = true;while （ok）{for （i = 0; i < maxn; ++i） node[i].clear（）;while （true）{if （gets（s） == 0）{ok = false;break;}if （s[0]）{sscanf（s, "%d%d%d", &u, &v, &l）;node[u].push_back（make_pair（v, l））;node[v].push_back（make_pair（u, l））;}else break;}ans = 0;dfs（1, 0）;printf（"%d
", ans）;}return 0;}