성대나라의 물탱크 (백준 18227)

안녕하세요. 오늘은 물탱크에 물을 채울 거예요.

문제

https://www.acmicpc.net/problem/18227

아이디어

이 문제에서의 핵심 관찰이 있습니다.
바로 한 도시는 한번 물을 받을 때 일정한 양을 받는다는 것입니다.
그래서 한 도시에 있는 물의 양은 (그 도시가 한번에 받는 물의 양)x(물을 받은 횟수)로 정의할 수 있습니다.
그 도시가 한번에 받는 물의 양은 그 도시의 깊이 (depth)가 됩니다. 이는 DFS로 쉽게 구할 수 있습니다.
물을 받은 횟수는 그 노드의 자식들(자신을 포함한)이 물을 받은 횟수와 동일해집니다. 그래서 이를 빠르게 구해야합니다. 그래서 쓰이는 두 알고리즘이 바로 오일러 경로 테크닉과 세그먼트 트리입니다. 이는 회사문화 3문제와 굉장히 유사합니다.

소스코드

#include <iostream>
#include <vector>
#define ll long long
using namespace std;

ll cnt = 0, EulerNum[202020] = { 0 }, depth[202020] = { 0 }, Start[202020] = { 0 }, End[202020] = { 0 };
vector <ll> v[202020];
void DFS(ll node, ll up)
{
    depth[node] = depth[up] + 1;
    EulerNum[node] = ++cnt;
    Start[node] = cnt;
    for (ll next : v[node])
        if (next != up)
            DFS(next, node);
    End[node] = cnt;
}

ll tree[808080] = { 0 };
ll SUM(ll s, ll e, ll node, ll l, ll r)
{
    if (e < l || r < s) return 0;
    if (l <= s && e <= r) return tree[node];
    ll mid = (s + e) / 2;
    return SUM(s, mid, node * 2, l, r) + SUM(mid + 1, e, node * 2 + 1, l, r);
}
void change(ll s, ll e, ll node, ll idx) //idx번지에 1 추가
{
    if (e < idx || idx < s) return;
    tree[node]++;
    if (s == e) return;
    ll mid = (s + e) / 2;
    change(s, mid, node * 2, idx);
    change(mid + 1, e, node * 2 + 1, idx);
}

int main(void)
{
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    ll N, C, i, a, b, M;

    cin >> N >> C;
    for (i = 0; i < N - 1; i++)
    {
        cin >> a >> b;
        v[a].push_back(b);
        v[b].push_back(a);
    }
    DFS(C, 0);

    cin >> M;
    for (i = 0; i < M; i++)
    {
        cin >> a >> b;
        if (a == 1)
            change(1, N, 1, EulerNum[b]);
        else
            cout << SUM(1, N, 1, Start[b], End[b]) * depth[b] << "\n";
    }
}

감사합니다.