백준 28472 - Minimax Tree (C++)

문제

• 문제 링크

  
   BOJ 28472 - Minimax Tree 
  

• 문제 요약

$N$개의 정점으로 이루어진 트리가 주어진다.
이 트리로 $Minmax$ $Tree$를 구성할 때, 각 정점의 답을 묻는 $Q$개의 쿼리에 답해보자.

• 제한

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




$2 ≤ N ≤ 10^5$

$1 ≤ Q ≤ 10^5$

$0 ≤ t_i ≤ 10^9$

알고리즘 분류

• 다이나믹 프로그래밍 (dp)
• 트리 (trees)
• 트리에서의 다이나믹 프로그래밍 (dp_tree)

풀이

기본적인 $TreeDP$ 문제이다.

문제에서 친절하게 규칙을 나열해주므로, 이를 그대로 코드에 옮겨주면 되겠다.

구체적으로 루트의 깊이를 $1$이라고 할 때, 리프 노드를 향해 내려가며

현재 깊이가 홀수라면 자식 노드의 최댓값을

현재 깊이가 짝수라면 자식 노드의 최솟값을

취해주면 된다.

그 외 어려울만한 부분은 없어 보이므로 자세한 설명은 생략.

전체 코드

#include<bits/stdc++.h>
#define N 100001
using namespace std;
 
vector <int> Gr[N], dp(N, -1);
int n, r;
 
void Input()
{
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> n >> r;
 
    for (int i{}; ++i < n;)
    {
        int u, v; cin >> u >> v;
        Gr[u].push_back(v);
        Gr[v].push_back(u);
    }
 
    int l; cin >> l;
    for(int k, t; l--; dp[k] = t)
        cin >> k >> t;
}
void Init(int now, int prev, int dep)
{
    if (!~dp[now])
    {
        dp[now] = dep & 1 ? -1e9 : 1e9;
        for (int& next : Gr[now])
            if (next ^ prev)
            {
                Init(next, now, dep + 1);
                dp[now] = dep & 1 ? max(dp[now], dp[next]) : min(dp[now], dp[next]);
            }
    }
}
void Query()
{
    int q; cin >> q;
    for (int x; q--; cout << dp[x] << '\n')
        cin >> x;
}
int main()
{
    Input();
    Init(r, r, 1);
    Query();
}

comment

끝