백준14268 내리 갈굼 2

작성일 | In

문제 링크

  • http://icpc.me/14268

사용 알고리즘

  • FenwickTree

시간복잡도

  • O(n + m log n)

풀이

트리에서 discovery time과 finish time을 미리 구해준 뒤, 각각 in과 out이라는 배열에 저장합시다. 방법을 모른다면 (이 글)의 앞 부분을 참고하시면 됩니다.

이 문제에서는 어떤 노드가 갈굼을 당하면, 자손들에게 전파를 해줍니다. 어떤 노드 i를 루트로 하는 서브 트리에 있는 모든 노드는 discovery time이 i보다 크거나 같고, finish time은 i보다 작거나 같습니다. 이러한 점을 이용해서 in[i]부터 out[i]까지 segment tree나 fenwick tree를 이용해 갈굼의 수치를 갱신해주면 됩니다.

전체 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
#include <bits/stdc++.h>
using namespace std;

int n, m;
int in[101010], out[101010];
int tree[101010];
vector<int> g[101010];

void update(int x, int val){
	for(int i=x; i<=n; i += (i&-i)){
		tree[i] += val;
	}
}

int query(int x){
	int ret = 0;
	for(int i=x; i>0; i -= (i&-i)){
		ret += tree[i];
	}
	return ret;
}

int cnt;

int dfs(int v){
	in[v] = ++cnt;
	for(auto u : g[v]){
		dfs(u);
	}
	out[v] = cnt;
}

int main(){
	ios_base::sync_with_stdio(0); cin.tie(0);
	cin >> n >> m;

	for(int i=1; i<=n; i++){
		int t; cin >> t;
		if(i == 1) continue;
		g[t].push_back(i);
	}

	dfs(1);

	while(m--){
		int op, x, y; cin >> op;
		if(op == 1){
			cin >> x >> y;
			update(in[x], y); update(out[x]+1, -y);
		}else{
			cin >> x;
			cout << query(in[x]) << "\n";
		}
	}
}