1. 1번 노드를 최상위 노드라고 가정하고 품
2. 1번 노드부터 시작하여 트리를 밑으로 탐색함.
3. 끝까지 닿으면, 거리를 올리면서(bottom-top) 다시 위로 올라감(재귀로 탐색하면 됨)
4. 한 노드에서 재귀로 반환하는 건, 자신의 자식 노드에서 올라오는 것중 가장 큰 값(끝까지 갔을 때의 값들 중 가장 큰 값)
5. 또 한 노드에선, 자식 노드에서 올라오는 것 중 가장 큰 값 2개를 저장하여, 탐색이 끝나면, 그 두개의 합이 전역으로 저장되어있는 length값보다 크면 저장.
6. 탐색이 모두 끝나면, 전역 length에 트리의 지름이 저장되어있음
코드
#include <iostream>#include <vector>#include <algorithm>using namespace std;vector<pair<int, int>> point[100001];int N, maxLength;bool check[100001];long long getLength(int cur);long long max(long long a, long long b) { return a > b ? a : b;}int main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin >> N; for (int i = 1; i <= N; i++) { int cur, a, b; cin >> cur; cin >> a; while (a != -1) { cin >> b; point[cur].push_back({ a, b }); cin >> a; } } getLength(1); cout << maxLength;}long long getLength(int cur) { check[cur] = true; bool isLast = true; long long result[2] = { 0, 0 }; for (int i = 0; i < point[cur].size(); i++) { if (!check[point[cur][i].first]) { long long tmp = getLength(point[cur][i].first) + point[cur][i].second; result[1] = max(result[1], tmp); if (result[1] > result[0]) { tmp = result[0]; result[0] = result[1]; result[1] = tmp; } isLast = false; } } if (isLast) return 0; else { maxLength =max(maxLength, result[0] + result[1]); return max(result[0], result[1]); }}