백준 26615 - 다오의 행사 계획하기 (C++)

문제 문제 링크 BOJ 26615 - 다오의 행사 계획하기 문제 요약 $N*N$ 크기 미로 모양의 행사장이 주어진다. 이곳에서 임의로 $K$개의 행사가 발생할 때, $T$일 간의 사람 수 변화를 구해보자.

제한 TL : $1$ sec, ML : $512$ MB $2 ≤ N, M$ $N * M ≤ 10^5$ $1 ≤ T, K ≤ 10^5$ 알고리즘 분류 트리(trees) 최소 공통 조상(lowest common ancestor) 누적 합(prefix_sum) 풀이 임의의 두 칸을 잇는 경로는 정확히 1개 있음이 보장된다고 한다. 즉, 미로는 트리이다.

두 칸을 잇는 경로에 대해 $V_i$명의 사람이 증가할 때, 영향 받는 칸의 수는 $LCA$ $With$ $Sparse$ $Table$ 을 이용해 $O(lo.....