백준 13016 내 왼손에는 흑염룡이 잠들어 있다 (c++)

문제 URL : https://www.acmicpc.net/problem/13016

 

문제접근법 : 

트리에서 모든노드중 가장 먼거리들을 전부 구하는문제입니다.

이문제를 풀기위해서 트리의 지름을 확인해야합니다.

트리의 지름을 확인해야합니다. 트리라는 성질로인해

모든노드의 가장먼거리는 지름의 끝점이기때문에 그 끝점에서의 거리로 가장 먼거리를

저장하기때문에 dfs를 3번만 돌리면 충분히 구할수있습니다.

 

소스코드 : 

//By 콩순이냉장고
#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll n;
vector<pair<ll,ll>> v[100000];
vector<ll>res;
ll _max = -1;
int start= -1;
void input(){
    cin>>n;
    ll a,b,c;
    for(int i =0;i<n-1;i++){
        cin>>a>>b>>c;
        v[a].push_back({b,c});
        v[b].push_back({a,c});
    }
}
void dfs(int cur,int parent=-1,ll sum=0){
    res[cur]=max(res[cur],sum);
    if(sum>_max){
        start=cur;
        _max=sum;
    }
    for(auto [next,cost] : v[cur]){
        if(next==parent)continue;
        dfs(next,cur,sum+cost);
    }
}
void solve(){
    res = vector<ll>(n+1);
    start=1;
    for(int i=0;i<3;i++){
       _max = -1;
       dfs(start);
    }
    for(int i=1;i<=n;i++)cout<<res[i]<<"\n";
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    input();
    solve();
}

궁금한점 혹은 모르는점 어떤질문이든 댓글은 언제나 환영입니다.