Solution: Subtrees & Paths | Heavy-Light Decomposition · USACO Guide

Table of Contents

Explanation Implementation

Table of Contents

Explanation Implementation

Official Editorial (C++, Java)

Explanation

This problem is a classic implementation of Heavy Light Decomposition.

Implementation

Time Complexity: $\mathcal{O}(\log^2N)$ per query

C++

#include <bits/stdc++.h>
using namespace std;

 Code Snippet: Lazy Segment Tree (Click to expand)

 Code Snippet: HLD (Click to expand)

int main() {

	int n, q;

Join the USACO Forum!

Stuck on a problem, or don't understand a module? Join the USACO Forum and get help from other competitive programmers!