[BOJ] 백준 14268 내리 갈굼 2

문제 링크

트리의 한 노드가 갈굼당하면 그 자식들이 모두 갈굼당해야한다. 구간이 보인다. 트리를 평평하게 펴서 세그먼트 트리로 만들고, lazy propagation을 적용하자.

비슷한 문제로 15782 Calculate! 2 가 있다. 트리를 펴는 자세한 설명은 해당 링크를 보자.

위 링크와 차이점은 이번에는 pre-order로 순회했다는 것이다. 

두 배열 $l$과 $r$, 주어진 트리의 어떤 정점 x에 대해 $l[x]$는 세그먼트 트리에서 x의 시작 구간이고 $r[x]$는 끝 구간이다.

이를 dfs로 쉽게 구할 수 있다.

$l[x]$는 순회하는 순서로 값을 채워넣으면 된다.

$r[x]$는 모든 자식들을 순회한 뒤 $l[x]$에서 자식 수만큼 증가시켜 넣어준다. (이는 세그먼트 트리에서 x의 마지막 자식의 위치이다)

또한 쿼리에 답할 때, 구간에 대해 묻는 게 아니라 한 정점에 대해 묻는 것이므로 구간 i, j를 받지 않고 정점 위치 idx만 받는다. 그냥 i, j 쿼리를 구현해서 같은 값을 넣어줘도 된다.

정답 코드

	#include <iostream>
	#include <vector>
	using namespace std;
	int n, m, lazy[400001], tree[400001], l[100001], r[100001];
	vector<vector<int>> p;
	void dfs(int now, int &o) {
	l[now] = ++o;
	for (int next : p[now]) {
	dfs(next, o);
	}
	r[now] = o;
	}
	void update_lazy(int node, int s, int e) {
	if (lazy[node]) {
	tree[node] += (e - s + 1)*lazy[node];
	if (s != e) {
	lazy[node * 2] += lazy[node];
	lazy[node * 2 + 1] += lazy[node];
	}
	lazy[node] = 0;
	}
	}
	void update(int node, int s, int e, int i, int j, int v) {
	update_lazy(node, s, e);
	if (j < s || e < i) return;
	if (i <= s && e <= j) {
	tree[node] += (e - s + 1)*v;
	if (s != e) {
	lazy[node * 2] += v;
	lazy[node * 2 + 1] += v;
	}
	return;
	}
	int m = (s + e) / 2;
	update(node * 2, s, m, i, j, v);
	update(node * 2 + 1, m + 1, e, i, j, v);
	tree[node] = tree[node * 2] + tree[node * 2 + 1];
	}
	int query(int node, int s, int e, int idx) {
	update_lazy(node, s, e);
	if (idx < s || e < idx) return 0;
	if (s == e) return tree[node];
	int m = (s + e) / 2;
	return query(node * 2, s, m, idx) + query(node * 2 + 1, m + 1, e, idx);
	}
	int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cin >> n >> m;
	p.resize(n + 1);
	int x;
	cin >> x;
	for (int i = 2; i < n + 1; i++) {
	cin >> x;
	p[x].push_back(i);
	}
	int o = 0;
	dfs(1, o);
	int c, y;
	for (int i = 0; i < m; i++) {
	cin >> c;
	if (c == 1) {
	cin >> x >> y;
	update(1, 1, n, l[x], r[x], y);
	}
	else if (c == 2) {
	cin >> x;
	cout << query(1, 1, n, l[x]) << '\n';
	}
	}
	}

view raw 14268.cpp hosted with ❤ by GitHub

질문 및 피드백 환영합니다.