백준 20924 - 트리의 기둥과 가지 (C++)

문제

• 문제 링크

  
   BOJ 20924 - 트리의 기둥과 가지 
  

• 문제 요약

$N$개의 정점으로 이루어진 트리가 주어진다.
이 트리의 '기둥의 길이' 와 '가장 긴 가지의 길이' 를 구해보자.

• 제한

TL : $2.5$ sec, ML : $1024$ MB




$1 ≤ N ≤ 10^6$

$1 ≤ C_i ≤ 10^9$

알고리즘 분류

• 그래프 이론(graphs)
• 그래프 탐색(graph_traversal)
• 트리(trees)
• 깊이 우선 탐색(dfs)

풀이

별로 설명이 필요한 부분이 없다.
문제에 정의된 데로 $dfs$를 이용해 슥슥 잘 구현해 주면 된다.

예제도 친절한 편.

전체 코드

#include<bits/stdc++.h>
using namespace std;
 
vector <pair<int, int>> Gr[200001];
int n, r, x, y;
 
void f(int p, int q, int s, int k)
{
    if (!k && p ^ r && Gr[p].size() > 2) k++, x = s, s = 0;
    if (p ^ r && Gr[p].size() == 1) (k ? y : x) = max(y, s);
    for (auto& [v, w] : Gr[p])
        if (v ^ q)
            f(v, p, s + w, k);
}
int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> n >> r;
    for (int i, j, w, o{}; ++o < n;)
        cin >> i >> j >> w, Gr[i].emplace_back(j, w), Gr[j].emplace_back(i, w);
    f(r, r, 0, Gr[r].size() > 1);
    cout << x << ' ' << y;
}

comment

끝