[백준] 1967번 트리의 지름

문제 출처: https://www.acmicpc.net/problem/1967

1967번: 트리의 지름

플로이드, 다익스트라를 이용해서는 시간초과가 될 것이다.

각 정점은 재귀적으로 가장 긴 길이의 자식 ~ 자신까지의 길이를 반환한다.

7번과 8번은 0을 리턴,

4번 노드는 7번노드가 만들 수 있는 길이인 0과 7번~4번까지 길이인 1을 더하여 1을 구하고

8번노드도 동일하게 0과 7을 더하여 7을 구한다.

이후 maxLeng이 1+7보다 작다면 값을 업데이트 해준다.

그리고 4번 노드는 (자신을 호출한) 2번노드에게 7을 리턴한다.

#include<iostream>
#include<vector>
#include<algorithm>


using namespace std;
typedef pair<int, int>P;
vector<P> adj[10001];
int maxLeng = 0;

int dfs(int root) {
	
	//터미널 노드일 경우
	if (adj[root].empty()) {
		return 0;
	}

	int max = 0, max2 = 0;
	
	for (int i = 0; i < adj[root].size(); i++) {
		int temp = dfs(adj[root][i].first) + adj[root][i].second;
		if (max < temp) {

			if (max2 < max) {
				max2 = max;
			}

			max = temp;
		}
		else if (max2 < temp) {
			max2 = temp;
		}
	}

	if (maxLeng < max + max2) {
		maxLeng = max + max2;
	}



	return max;

}




int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
 
	int n;
	cin >> n;


	for (int i = 0; i < n-1; i++) {
		int pa, ch, val;
		cin >> pa >> ch >> val;
		//adj[부모] = P(자식,가중치)
		adj[pa].push_back(P(ch, val));
	}

	int max = dfs(1);

	cout << maxLeng;





}