백준 29619 - 나무나무나 심어야지 (C++)

문제

• 문제 링크

  
   BOJ 29619 - 나무나무나 심어야지 
  

• 문제 요약

최초 $N$개의 정점으로 이루어진 트리에서, 아래와 같은 유형으로 이루어진 $Q$개의 쿼리가 주어진다.
각 쿼리를 알맞게 처리해보자.

쿼리를 간단히 요약하자.



$1$ $i$ $j$ $w$ : $i$번 정점에 $j$번 정점을 추가한다. 이때 $j$는 정점값 $w$를 가진다.

$2$ $i$ : $i$번 정점을 루트로 하는 서브 트리의 모든 정점값의 합을 출력한다.

• 제한

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




$2 ≤ N, Q ≤ 100,000$

$0 ≤ w_i ≤ 500$

알고리즘 분류

• 자료 구조 (data_structures)
• 트리 (trees)
• 세그먼트 트리 (segment tree)
• 오일러 경로 테크닉 (euler_tour_technique)
• 오프라인 쿼리 (offline_queries)

풀이

트리의 모양이 바뀌지 않고, 아래의 두 쿼리를 처리하는 문제를 푼다고 해보자.

$1$ $i$ $w$ : $i$번 정점의 정점값을 $w$로 바꾼다.

$2$ $i$ : $i$번 정점을 루트로하는 서브 트리의 모든 정점값의 합을 출력한다.

선형 구조였다면 $Segment$ $Tree$ 등으로 간단하게 풀 수 있다.
하지만 트리이기 때문에, 이를 적용하기 위해선 트리를 선형 구조처럼 볼 수 있게 하는 작업이 필요하다.

이때 사용되는 테크닉이 $Euler$_$Tour$_$Technique$ 이다.
이 테크닉이 생소하다면, 인터넷에 많은 좋은 글들이 있으니 개념을 정립 후 다시 돌아오도록 하자.


결국 $1$번 쿼리는 $in[i]$의 정점값을 $w$로 업데이트, $2$번 쿼리는 $in[i], out[i]$의 구간 합으로써 처리할 수 있게 된다.

---

이제 문제로 돌아와서 생각해보면, 느낌이 빡 올 것이다.

쿼리를 모두 받아놓고, 최대 $N+Q-1$개의 정점으로 이루어질 수 있는 트리를 구성하자.

이후 정점값들을 $in[1], in[2], ... in[N]$에만 업데이트하자.

그럼 $1$번 쿼리는 곧 $in[j_i]$의 정점값을 $w_i$로 업데이트하는 것과 같다.

전체 코드

#include<bits/stdc++.h>
#define N 200001
using namespace std;
 
struct _Q { int op, i; } Q[N >> 1];
vector <int> Gr[N], seg(1 << 19);
int in[N], out[N];
int n, q, w[N];
 
void Input()
{
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> n >> q;
 
    int i(1), x; cin >> x;
    while (++i <= n)
    {
        cin >> x;
        Gr[x].push_back(i);
    }
 
    for (int i(1); i <= n; cin >> w[i++]);
    for (int i{}; i < q; i++)
    {
        cin >> Q[i].op >> Q[i].i;
        if (Q[i].op & 1)
        {
            int sub; cin >> sub;
            cin >> w[sub];
 
            Gr[Q[i].i].push_back(sub);
            Q[i].i = sub;
        }
    }
}
 
int cur;
void ETT(int now)
{
    in[now] = ++cur;
    for (int& next : Gr[now])
        ETT(next);
    out[now] = cur;
}
int segUpdate(int n, int s, int e, int i, int val)
{
    if (s > i || e < i) return seg[n];
    if (s == e) return seg[n] = val;
    int m(s + e >> 1);
    return seg[n] = segUpdate(n << 1, s, m, i, val) + segUpdate(n << 1 | 1, m + 1, e, i, val);
}
int segQuery(int n, int s, int e, int l, int r)
{
    if (s > r || e < l) return 0;
    if (s >= l && e <= r) return seg[n];
    int m(s + e >> 1);
    return segQuery(n << 1, s, m, l, r) + segQuery(n << 1 | 1, m + 1, e, l, r);
}
void Solve()
{
    for (int i(1); i <= n; i++)
        segUpdate(1, 1, n + q, in[i], w[i]);
 
    for (int i{}; i < q; i++)
    {
        if (Q[i].op & 1)
            segUpdate(1, 1, n + q, in[Q[i].i], w[Q[i].i]);
        else
        {
            int ans(segQuery(1, 1, n + q, in[Q[i].i], out[Q[i].i]));
            cout << (ans ? ans : -1) << '\n';
        }
    }
}
int main()
{
    Input();
    ETT(1);
    Solve();
}

comment

끝