Graph Theory37 sections · 1633 units
Open in Course

Problem - Blood Cousins

Codeforces 208E, LCA + Eule...

You are given a rooted tree. Answer queries of this form: how many nodes are at depth exactly d and have their LCA with node v at depth exactly h?

In other words, count v's "cousins" at a specific depth and distance. You are filtering by both depth and ancestor level. There are up to 100100,000000 nodes and 100100,000000 queries. You need efficient filtering.

The approach: lift v to depth h using binary lifting. Then count descendants of that ancestor at depth d. Euler tour flattening helps make the counting efficient.