코딩하는 두꺼비

www.acmicpc.net/problem/1967

하루 넘게 고민해서 겨우 푼 문제이다..

처음엔 단순히 2개의 간선을 가지는 노드들을 dfs 두번 보내서 각각의 간선 가중치의 합을 더하고 그 중 최댓값을 출력하게 풀려했는데 잘 안되었다.

반례를 보고 깨달았는데 이진 트리가 아니라서 간선이 한 방향에만 있는 경우, 여러개 있는 경우를 고려해주어야 했던 것이다.

그래서 런타임 에러 등을 통해 고생하다가 결국 풀 수 있었다.

1. 간선의 내용을 모두 받아오고 2개 이상의 간선을 가지는 노드를 따로 빼준다. (1은 초기 상태로 무조건 넣어줌)

2. 그렇게 구한 노드들을 모두 확인하는데, 각 노드의 아래에 있는 간선들의 합을 더해주되, 최댓값과 그 두번째 값을 저장하여 정답 벡터에 넣어준다.

3. 정답 벡터에 들어가 있는 값들 중 최댓값 출력

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

vector <pair<int, int>> v[10001];
vector<int> v2;
vector<int> ans;
int cnt[10001];
int x, n;

void dfs(int b, int c) {
	if (v[b].empty()) {
		x = max(x, c);
		return;
	}
	for (int j = 0; j < v[b].size(); j++) {
		c += v[b][j].second;
		dfs(v[b][j].first, c);
		c -= v[b][j].second;
	}

}

int main() {
	int a, b, c;
	cin >> n;
	if (n == 1) {
		cout << 0;
		return 0;
	}
	for (int i = 0; i < n-1; i++) {
		cin >> a >> b >> c;
		v[a].push_back({ b,c });
		cnt[a]++;
	}
	v2.push_back(1);
	for (int i = 2; i <= n; i++) {
		if (cnt[i] > 1) {
			v2.push_back(i);
		}
	}
	for (int i = 0; i < v2.size(); i++) {
		int res = 0;
		int m1 = 0, m2 = 0;
		for (int j = 0; j < v[v2[i]].size(); j++) {
			dfs(v[v2[i]][j].first, v[v2[i]][j].second);
			m2 = max(m2, min(m1,x));
			m1 = max(m1, x);
			x = 0;
		}
		ans.push_back(m1+m2);
	}
	cout << *max_element(ans.begin(), ans.end());
	return 0;
}