[백준] 2820 자동차 공장

문제

상근이는 자동차를 매우 좋아한다. 자동차 공장에 취직한 상근이는 계속된 승진 끝에 드디어 사장이 되었다. 공장에는 총 N명의 직원이 있다. 상근이를 제외한 모든 직원은 한 명의 상사가 있다. (상근이는 모든 사람의 상사이다) 상근이의 번호는 1번이고, 나머지 직원의 번호는 2부터 N이다.

모든 직원은 자신의 모든 부하 직원(직속 부하와 부하의 부하등등을 모두 포함)의 월급을 인상하거나 삭감할 수 있다. 상근이는 권력 남용을 막기 위해 직원의 월급을 모니터링 하려고 한다.

월급의 변화를 모니터링하는 프로그램을 작성하시오.

모든 직원의 월급은 항상 양의 정수이고 231-1 이하이다.

입력

첫째 줄에 직원의 수 N과 월급 변화와 조사 쿼리의 수 M이 주어진다. (1 ≤ N, M ≤ 500,000)

다음 N개 줄의 i번째 줄에는 직원 i의 초기 월급과 상사의 번호가 주어진다. (상근이는 상사가 없기 때문에, 초기 월급만 주어진다)

다음 M개 줄에는 월급 변화와 조사 쿼리가 주어진다.

1. p a x가 주어진 경우 a의 모든 부하의 월급을 x만큼 증가시킨다. (-10,000 ≤ x ≤ 10,000)
2. u a가 주어진 경우에는 a의 월급을 출력한다.

출력

입력으로 u가 주어질 때마다 해당하는 직원의 월급을 출력한다.

 

상근이의 자동차 공장의 직원구조는 트리형태입니다. 각 직원은 한 명의 상사가 있는 구조입니다.

어떤 직원은 모든 자신의 부하직원의 월급을 인상/삭감할 수 있습니다.

따라서 세그먼트 트리구조를 만들면 됩니다.

또한, 업데이트가 자주 발생하므로 느리게 갱신되는 세그먼트트리를 사용하면 됩니다.

 

중요한건,,인덱싱입니다.

p a x 는 a의 부하의 월급을 변화시키는것이므로

dfs를 이용해 인덱싱을 할 때 조심해야합니다.

 

또한, 인덱싱을 하게되면, 초기 월급배열의 위치 또한 바뀌어야합니다.

이를 조심해서 dfs를 수행하고, 

init함수로 세그트리를 구성,

update와 query를 수행하면 됩니다.

 

#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;
ll N, M, lazy[2000014], seg[2000014], cnt = 1, m[500001], from[500001], to[500001],a[500001];
vi adj[500001];
void index(int k) {
	from[k] = ++cnt; //각 직원은 자신의 월급을 조정할 수 없습니다
	a[cnt - 1] = m[k]; //k번 직원은 cnt-1번으로 인덱스가 바뀌었습니다.
	for (int r : adj[k]) {
		index(r);
	}
	to[k] = cnt - 1;
}
void propagate(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];
		lazy[n] = 0;
	}
}
//update(1, N, 1, from[a], to[a], x);
void update(int l, int r, int n, int f, int t, ll x) {
	propagate(l, r, n);
	if (r < f || t < l)return;
	if (f <= l && r <= t) {
		lazy[n] += x;
		return;
	}
	int mid = (l + r) / 2;
	update(l, mid, n * 2, f, t, x);
	update(mid + 1, r, n * 2 + 1, f, t, x);
}
ll query(int l, int r, int n, int t) {
	propagate(l, r, n);
	if (r < t || t < l)return 0;
	if (l==t && r==t) {
		return seg[n];
	}
	int mid = (l + r) / 2;
	return query(l, mid, n * 2, t) + query(mid + 1, r, n * 2 + 1, t);
}
ll init(int l, int r, int n) {
	if (l == r)return seg[n] = a[l];
	int mid = (l + r) / 2;
	return seg[n] = init(l, mid, n * 2) + init(mid + 1, r, n * 2 + 1);
}
int main(){
	FAST;
	cin >> N >> M;
	cin >> m[1];
	for (int i = 2; i <= N; i++) {
		int x;
		cin >> m[i] >> x;
		adj[x].push_back(i);
	}
	index(1);
	init(1,N,1);
	while (M--) {
		char c;
		cin >> c;
		if (c == 'p') {
			ll a, x;
			cin >> a >> x; //a의 모든 부하직원의 월급을 x만큼 증가시킨다
			update(1, N, 1, from[a], to[a], x);
		}
		else {
			ll a;
			cin >> a; //a의 월급을 출력한다
			cout <<query(1, N, 1, from[a]-1) << "\n";
		}
	}
}