Skip to main content

Practice · 2 of 3

Deep Subtrees

CHALLENGE
Difficulty: advanced+25 XP

**Problem.** Line 1: n. Then n-1 lines: parent of v (2..n), parent(1) omitted. Then q and q node ids. Print each subtree size. **Constraints:** 1 ≤ n ≤ 200000; 1 ≤ q ≤ 200000; the tree may be a bamboo of depth n. Recursive DFS of depth 2e5 crashes; go iterative.

Back to lesson: Practice: Bug Hunt