[BOJ 14268]

문제 바로가기 : https://www.acmicpc.net/problem/14268
같은 유형, BOJ 2820 : https://www.acmicpc.net/problem/2820
문제 설명은 위 링크에서 확인해주시길 바랍니다.
상사-부하 간에 관계를 정리하기 위해 pre-order로 순회했으며 degurii님의 글을 참고했습니다. 감사합니다.

Solution

review

lazy propagation 응용 문제다. 상사와 부하의 관계가 정해져 있다는 점이 특징이다.
특정 부하가 칭찬받으면 그 부하 밑에 있는 부하들도 포함해서 모두 칭찬을 받는다. 칭찬받는 수치도 정해져있다.
특정 직원 번호를 넣었을 때 본인부터 그 직원의 마지막 부하 번호까지 나타낼 방법이 필요하게 된다.
나타낼 수 있게 됐다면 해당 범위(구간)에 칭찬 횟수만큼 더해주면 된다.

직원 본인(s[who])부터 마지막 부하 번호(e[who])까지 나타내는 방법은 다음과 같다.

//cur의 시작(s[cur]) 및 끝(e[cur]) 구간을 정의
void dfs(int cur, int& num) {
    s[cur] = ++num;
    for (auto& next : p[cur])
        dfs(next, num);
    e[cur] = num;