355. Nodes Exactly K Away
Print how many nodes are exactly k edges away from the node holding value
x. Distance is measured in either direction: downwards into subtrees, upwards
through the parent, and across into a sibling's subtree.
This is the problem where a tree has to be treated as a GRAPH. Every earlier
problem here only ever moved downwards, and a node k away may lie above the
starting point or in a completely different branch.
Build parent links so each node has three neighbours: left child, right child
and parent. Then a breadth-first search from the starting node reaches everything
at distance k in one sweep, exactly as it would in a graph.
Mark nodes as visited. Without that, the search walks back down the way it came and counts nodes twice.
Constraints - `1 ≤ n ≤ 100000` - `0 ≤ k ≤ 100000` - `-1000000000 ≤ value ≤ 1000000000` - All values are distinct, and `x` appears in the tree. - The input always forms a valid tree rooted at node 1.
Input
The first line contains three integers n, x and k.
The second line contains n values, where node i holds the ith value.
Each of the next n lines contains the left and right child of node i,
using 0 for no child. Node 1 is the root.
Output
Print one integer, the number of nodes exactly k edges from the node holding x.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.