아쉬움이 남지만 (BOJ 18862) https://www.acmicpc.net/problem/18862 정점 $x$의 부모 정점의 번호를 $p(x)$, 정점 $x$의 높이를 $h(x)$라고 하자. 이 때 정점 $c$의 조상 정점 $x$에서 정점 $c$까지 점프했을 때의 높이 $j(x, c)$는 아래와 같이 계산된다.$$j(x, c)=\sum\limits_{i=0}^{depth(c)-depth(x)}{\frac{h(p^{i}(c))}{2^{i+1}}}+\frac{h(x)}{2^{depth(c)-depth(x)+1}}$$$$j(p(x), c)-j(x, c)=\frac{h(p(x))-h(x)}{2^{depth(c)-depth(x)+1}}$$ dfs를 통해 깊이 있는 정점부터 답을 구하면서, $dfs(x)$에서 $H[c]=\lfloor j(x, .. 더보기 이전 1 2 3 4 5 ··· 24 다음