Graph Theory37 sections · 1633 units
Open in Course

Walkthrough

(Example with range)

Tree: 123451-2-3-4-5 (line). Range: k1=1k_1=1, k2=3k_2=3. Centroid is 33. Distances from 33: {2,1,0,1,2}\{2,1,0,1,2\} for nodes {1,2,3,4,5}\{1,2,3,4,5\}. For node 11 (distance 22), look for distances in range [12,32]=[1,1][1-2, 3-2] = [-1, 1]. Since distances are non-negative, this is [0,1][0, 1]: nodes 33 and 2,42,4. That is 33 pairs.

For node 22 (distance 11), range [0,2][0, 2]: all nodes work. Continue this process for all nodes, subtract same-subtree pairs, and sum. The arithmetic gets complex but the pattern is clear.