트리와 쿼리 1 (JUNGOL 3600)

https://jungol.co.kr/problem/3600?cursor=MTIsMiww

---

아이디어

오일러 투어 테크닉을 통해서 모든 노드마다 방문 번호를 붙여줍시다. 그러면 어떠한 노드 x를 루트로 하는 서브트리에 존재하는 모든 노드들을 직선상의 하나의 구간으로 표현할 수 있게 됩니다. 그러면 세그먼트 트리를 이용해서 문제를 해결해줄 수 있게 됩니다.

---

소스코드

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

ll tree[1212121]={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 update(ll s,ll e,ll node,ll idx,ll num)
{
    if (idx<s || e<idx) return;
    if (s==e)
    {
        tree[node]=num;
        return;
    }
    ll mid=(s+e)/2;
    update(s,mid,node*2,idx,num);
    update(mid+1,e,node*2+1,idx,num);
    tree[node]=tree[node*2]+tree[node*2+1];
}

vector <ll> Graph[303030];
ll In[303030]={0},Out[303030]={0},cnt=0;
void DFS(ll node)
{
    In[node]=++cnt;
    for (ll next:Graph[node])
        if (In[next]==0)
            DFS(next);
    Out[node]=cnt;
}

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

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

    cin>>Q;
    for (i=0;i<Q;i++)
    {
        cin>>type;
        if (type==1)
        {
            cin>>a>>b;
            update(1,N,1,In[a],b);
        }
        else
        {
            cin>>a;
            cout<<Sum(1,N,1,In[a],Out[a])<<"\n";
        }
    }
}