Centroid Decomposition
트리에서 센트로이드를 잡고 분할 정복을 돌리는 테크닉. 5820번: 경주 첫째 줄에 N과 K가 주어진다. 둘째 줄부터 N-1개 줄에는 H[i][0], H[i][1], L[i]가 주어진다. (1 ≤ N ≤ 200,000, 1 ≤ K ≤ 1,000,000) www.acmicpc.net #include using namespace std; typedef pair pii; const int N=2e5+1; const int K=1e6+1; const int INF=1e9; int n,k; int sz[N],use[N],chk[K]; vector ad[N]; vector tree; int get_size(int cur,int prv) { sz[cur]=1; for(auto [nxt,w] : ad[cur]){ if..
