하루 넘게 고민해서 겨우 푼 문제이다..
처음엔 단순히 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;
}