题解 | #最长路径#

1、随机选择一个点进行深度搜索，找到最长长度的尾节点，此尾节点必定为所求的最长路径的头节点（或尾节点，因为是无向图，最长路径的头节点也可以是尾节点）。推导过程：https://zhuanlan.zhihu.com/p/44391252。
2、从第一步找到的尾节点出发再找一次最长路径，就是结果。

class Solution {
public:
vector<vector<pair<int, int>>> road;
vector<int> visited;
int index_temp, length_temp = 0;
void get_max_length(int cur_index, int cur_length) {
int next_index, end_flag = 1;
visited[cur_index] = 1;
for (auto i : road[cur_index]) {
next_index = i.first;
if (!visited[next_index]) {
end_flag = 0;
get_max_length(next_index, cur_length + i.second);
}
}
visited[cur_index] = 0;
if (end_flag) {
if (cur_length > length_temp) {
length_temp = cur_length;
index_temp = cur_index;
}
}
}
long long solve(int n, vector<int>& u, vector<int>& v, vector<int>& w) {
// write code here
road.resize(n);
visited.resize(n, 0);
for (int index = 0; index < u.size(); ++index) {
road[u[index] - 1].push_back(make_pair(v[index] - 1, w[index]));
road[v[index] - 1].push_back(make_pair(u[index] - 1, w[index]));
}
get_max_length(0, 0); //这是第一步搜索，此处取0节点开始
get_max_length(index_temp, 0);
return length_temp;
}
};</int></int></int></int>