https://www.acmicpc.net/problem/13512 13512번: 트리와 쿼리 3 N개의 정점으로 이루어진 트리(무방향 사이클이 없는 연결 그래프)가 있다. 정점은 1번부터 N번까지 번호가 매겨져 있고, 간선은 1번부터 N-1번까지 번호가 매겨져 있다. 가장 처음에 모든 정점의 www.acmicpc.net Heavy-Light Decomposition 일단 트쿼 3을 풀기 전에, LCA 2를 HLD를 이용해서 풀어보자. 1. dfs를 통하여 한 노드를 루트로 하는 서브트리의 크기를 저장해둔다. 1 2 3 4 5 6 7 def dfs(x, p): par[x] = p sz[x] = 1 for i in g[x]: if i != p: sz[i] += dfs(i, x) return sz[x] cs..
