[BOJ]백준 1167번: 트리의 지름

1번 정점을 루트로 가정하고 dp[i]를 i번째 정점을 서브 트리의 루트로 가정했을때 가장 긴 지름을 저장함

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <memory.h>
#include <math.h>

using namespace std;
typedef pair<int, int> pii;
typedef long long ll;
int n;
vector<pii> v[100001];
int dp[100001]; // i 를 루트로 했을때 지름 길이
int recv(int node, int p) {
	int& ret = dp[node];
	if (~ret) return ret;
	ret = 0;
	int _max1 = 0, _max2 = 0;
	for (auto nxt : v[node]) {
		int _node = nxt.first;
		int dist = nxt.second;
		int cnt = 0;
		if (_node != p) {
			cnt = recv(_node, node) + dist;
			if (cnt > _max1) {
				if (cnt > _max2) {
					_max1 = _max2;
					_max2 = cnt;
				}
				else {
					_max1 = cnt;
				}
			}
		}
	}
	ret = _max1 + _max2;
	return _max2;
}
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL), cout.tie(NULL);
	cin >> n;
	memset(dp, -1, sizeof(dp));
	for (int i = 0; i < n; i++) {
		int num;
		cin >> num;
		while (1) {
			int a, b;
			cin >> a;
			if (~a) {
				cin >> b;
				v[num].push_back({ a,b });
			}
			else {
				break;
			}
		}
	}
	recv(1,-1);
	int ans = 0;
	for (int i = 1; i <= n; i++) {
		ans = max(ans, dp[i]);
	}
	cout << ans;
}