[ boj : 18126 ] 너구리 구구

https://www.acmicpc.net/problem/18126

18126번: 너구리 구구

문제 : 구구가 입구에서 가장 멀리 떨어져있는 곳에다가 아이스크림을 숨키려고 한다. 이때 그 길이를 구하자

해설 : 그냥 dfs 한번 돌려서 각 동작마다 최대값을 return 시켜주게끔 하면 됩니다. 주의할 점은 '오버플로' 잘 보세요.

#include<bits/stdc++.h>

using namespace std;
using ll = long long;
vector<pair<int, ll>> v[5010];
ll dfs(int x, int p);

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);

	int n;
	int a, b, c;
	cin >> n;

	for (int i = 0; i < n - 1; i++) {
		cin >> a >> b >> c;
		v[a].push_back({ b,c });
		v[b].push_back({ a,c });
	}
	cout<<dfs(1,-1);
	return 0;
}
ll dfs(int x,int p)
{
	ll ret = 0;
	for (int i = 0; i < v[x].size(); i++) {
		if (v[x][i].first == p)continue;
		ret = max(ret, dfs(v[x][i].first,x) + v[x][i].second);
	}
	return ret;
}