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

문제 링크 : [백준]성대나라의 물탱크(18227)

문제 설명

N개의 노드로 이루어진 트리가 존재합니다.
특정 노드에 물을 공급하려 하는데, 물을 공급하려면 루트 노드부터 해당 노드까지 각 깊이에 해당하는 만큼의 물을 넣어야 합니다.
물을 넣으면서 중간중간 특정 노드에 물이 얼마나 공급되었는지를 확인하세요.

입력

N(노드의 수, 1 <= N <= 200,000)
C(수도의 번호)
A_i B_i(두 노드간 연결 관계)
Q(쿼리의 수, 1 <= Q <= 200,000)
O_i N_i(쿼리 번호, 노드 번호)

7 1
1 2
1 3
1 4
2 5
4 6
4 7
8
1 6
2 1
2 4
2 6
1 1
2 1
2 4
2 6

출력

1
2
3
2
2
3

카테고리

#오일러경로 #세그먼트트리

시간 복잡도 상한

O(Q * logN)

해결 방법

• 자기를 포함한 자기 자식이 몇번 호출되었는지와 자신의 깊이가 몇인지를 알면 구할 수 있습니다.
• DFS를 돌면서, 자신의 자식들의 노드 번호를 순서대로 채번하면서 자식들의 범위를 설정합니다.
• 특정 노드가 물을 공급받게 되면, 새로 부여받은 노드 번호에 카운팅을 합니다.
• 조회 쿼리가 들어오면, 2에서 구한 자신의 자식노드들의 구간합을 세그먼트 트리를 이용하여 구합니다.

시간복잡도

O(Q * logN)

코드

#include<iostream>
#include<vector>
#define N 200001
using namespace std;
typedef long long L;
int n,s,i,d[N],e[N][2],w[N],a,b,k;
L t[N*4];
vector<int>v[N];
void r(int p){
    w[p]=e[p][0]=++k;
    for(int x:v[p])if(!d[x])d[x]=d[p]+1,r(x);
    e[p][1]=k;
}
L u(int p,int l,int r,int x){
    if(x<l||r<x)return t[p];
    if(l==r)return ++t[p];
    return t[p]=u(p*2,l,(l+r)/2,x)+u(p*2+1,(l+r)/2+1,r,x);
}
L q(int p,int l,int r,int x,int y){
    if(y<l||r<x)return 0;
    if(x<=l&&r<=y)return t[p];
    return q(p*2,l,(l+r)/2,x,y)+q(p*2+1,(l+r)/2+1,r,x,y);
}
int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin>>n>>s;
    for(i=0;i<n-1;i++){
        cin>>a>>b;
        v[a].push_back(b);
        v[b].push_back(a);
    }
    d[s]=1;
    r(s);
    cin>>k;
    while(k--){
        cin>>a>>b;
        if(a&1)u(1,1,n,w[b]);
        else cout<<q(1,1,n,e[b][0],e[b][1])*d[b]<<"\n";
    }
}