백준 23835 - 어떤 우유의 배달목록 (Easy) (C++)

문제

• 문제 링크

  
   BOJ 23835 - 어떤 우유의 배달목록 (Easy) 
  

• 문제 요약

$N$개의 정점으로 이루어진 트리가 주어진다.
$Q$개의 쿼리를 적절히 처리해보자.

• 제한

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




$1 ≤ N, Q ≤ 1,000$

알고리즘 분류

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

풀이

범위를 보면, $Eazy$ 버전 답게 굉장히 작다.
그냥 쿼리마다 $dfs$를 돌려 $O(QN)$의 복잡도를 가져도 널널해 보인다.

$Hard$ 버전은 딱봐도 $hld$ + 세그먼트 트리일 듯 한데, 구간에 등차수열을 더하는 문제인 이 문제 를 트리 위에서 진행 한다고 생각하면 될 것 같다.

조만간 도전해 봐야지..

전체 코드

#include<bits/stdc++.h>
#define N 1001
using namespace std;
 
vector <int> Gr[N];
int n, q, o, i, j, C[N];
 
int f(int p, int q, int c)
{
    int t(p == j ? c : 0);
    for (int x : Gr[p])
        if (!t && x ^ q)
            t = f(x, p, c + 1);
    return t ? (C[p] += t), c - 1 : 0;
}
int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0);
    for (cin >> n; o++ < n - 1;)
        cin >> i >> j, Gr[i].push_back(j), Gr[j].push_back(i);
    for (cin >> q; q--;)
    {
        cin >> o >> i;
        if (o & 1) cin >> j, f(i, 0, 0);
        else cout << C[i] << '\n';
    }
}

comment

끝