백준 소스코드 [C++] 1967 트리의 지름

www.acmicpc.net/problem/1967

1967번: 트리의 지름

백준 소스코드 [C++] 1967 트리의 지름

#include <iostream>
#include <algorithm>
#include <queue>
#include <string.h>
#include <limits.h>
#include <vector>
#include <math.h>
#include <stack>
#include <bitset>
#include <string>
#include <set>
#define all(v) v.begin(), v.end()
#define pii pair<int,int>
#define make_unique(v) v.erase(unique(v.begin(), v.end()), v.end())
typedef long long ll;
using namespace std;

vector<pii> v[10001];
int res[10001];
int sum[10001];
void dfs(int n) {
	if (v[n].size() == 0) {
		res[n] = 0;
		sum[n] = 0;
		return;
	}
	else if (v[n].size() == 1) {
		dfs(v[n][0].first);
		res[n] = v[n][0].second + sum[v[n][0].first];
		sum[n] = v[n][0].second + sum[v[n][0].first];
	}
	else {
		int k = v[n].size();
		for(int i=0;i<k;i++)
			dfs(v[n][i].first);
		vector<int>w;
		w.clear();
		for (int i = 0;i < k;i++)
			w.push_back(v[n][i].second + sum[v[n][i].first]);
		sort(all(w));
		res[n] = w[k - 1] + w[k - 2];
		sum[n] = w[k - 1];
	}
}
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	int n, a, b, c;
	cin >> n;
	for (int i = 1;i < n;i++) {
		cin >> a >> b >> c;
		v[a].push_back({ b,c });
	}
	dfs(1);
	int m = INT_MIN;
	for (int i = 1;i <= n;i++) {
		if (m < res[i]) m = res[i];
	}
	cout << m;
	return 0;
}