[백준] 14268 회사 문화 2

 

문제

영선회사에는 매우 좋은 문화가 있는데, 바로 상사가 직속 부하를 칭찬하면 그 부하가 부하의 직속 부하를 연쇄적으로 칭찬하는 내리 칭찬이 있다. 즉, 상사가 한 직속 부하를 칭찬하면 그 부하의 모든 부하들이 칭찬을 받는다.

모든 칭찬에는 칭찬의 정도를 의미하는 수치가 있는데, 이 수치 또한 부하들에게 똑같이 칭찬 받는다.

이번에는 내리 칭찬이 실시간으로 일어날 것이다.

입력으로 아래와 같은 쿼리가 주어질 것이다.

• 1 i w: i번째 직원이 직속 상사로부터 w만큼 칭찬을 받는다. (2 ≤ i ≤ n, 1 ≤ w ≤ 1,000)
• 2 i: i번째 직원이 칭찬을 받은 정도를 출력한다.

직속 상사와 직속 부하관계에 대해 주어지고, 쿼리가 주어졌을 때 2번 쿼리에 따라 출력한다.

입력

첫째 줄에는 회사의 직원 수 n명, 쿼리의 개수 m이 주어진다. 직원은 1번부터 n번까지 번호가 매겨져 있다. (2 ≤ n, m ≤ 100,000)

둘째 줄에는 직원 n명의 직속 상사의 번호가 주어진다. 직속 상사의 번호는 자신의 번호보다 작으며, 최종적으로 1번이 사장이다. 1번의 경우, 상사가 없으므로 -1이 입력된다.

다음 m줄에는 위와 같이 쿼리가 주어진다. 사장은 상사가 없으므로 칭찬을 받지 않는다.

출력

2번 쿼리가 주어질 때마다, 알맞게 출력하시오.

 

트리에서 lazy propagation 문제입니다.

dfs로 인덱싱만 하면 쉽게 풀립니다.

 

#include<bits/stdc++.h>
#define FAST ios_base::sync_with_stdio(false),cin.tie(NULL);
#define mset(v) memset(v,0,sizeof(v));
#define rep(i,a) for(int i=0;i<a;++i)
#define REP(i,a) for(int i=1;i<=a;++i)

using namespace std;

typedef long long ll;
typedef pair<int, int> pi;
typedef tuple<int, int, int>ti;
typedef vector<int> vi;
typedef vector<vector<int>> vvi;
int dy[] = { -1,0,1,0 }, dx[] = { 0,1,0,-1 }, INF = 987654321;

int N, M, lazy[400004], seg[400004], cnt = 1, from[100001], to[100001];
vi adj[100001];
void index(int k) {
	from[k] = cnt++;
	for (int r : adj[k]) {
		index(r);
	}
	to[k] = cnt - 1;
}
void prop(int l,int r,int n) {
	if (lazy[n]) {
		if (l != r) {
			lazy[n * 2] += lazy[n];
			lazy[n * 2 + 1] += lazy[n];
		}
		seg[n] += lazy[n]*(r-l+1);
		lazy[n] = 0;
	}
}
void update(int l, int r, int n, int f, int t, int a) {
	prop(l, r,n);
	if (r < f || t < l)return;
	if (f <= l && r <= t) {
		lazy[n] += a;
		return;
	}
	int mid = (l + r) / 2;
	update(l, mid, n * 2, f, t, a);
	update(mid + 1, r, n * 2 + 1, f, t, a);
}
ll query(int l, int r, int n, int t) {
	prop(l, r, n);
	if (r < t || t < l)return 0;
	else if (r == t && l == t)return seg[n];
	int mid = (l + r) / 2;
	return query(l, mid, n * 2, t) + query(mid + 1, r, n * 2 + 1, t);
}
int main(){
	FAST;
	cin >> N >> M;
	REP(i, N) {
		int x;
		cin >> x;
		adj[x].push_back(i);
	}
	index(1);
	while (M--) {
		int x;
		cin >> x;
		if (x == 1) {
			int a, b;
			cin >> a >> b; //a가 b만큼 칭찬을 받는다
			update(1, N, 1, from[a], to[a], b);
		}
		else {
			int a;
			cin >> a;//a가 칭찬받은 정도를 출력한다
			cout << query(1, N, 1, from[a]) << "\n";
		}
	}
}