Snail's Descent Turn-limited Path Counting

You are given a rooted tree with nodes numbered from \(1\) to \(n\), with node \(1\) as the root. For each node, the order in which its children appear is determined by the input. For a node with \(m\) children, the \(j\)th child is assigned a horizontal offset defined by \(d = j - \lceil m/2 \rceil\). A leaf is a node with no children.

A snail path is defined as a simple path from the root to a leaf. As the snail descends, it carries a notion of direction. For the edge from a parent to its child, the direction is the horizontal offset \(d\) (as defined above). For the root, define its incoming direction to be \(0\). When moving from a parent with incoming direction \(p\) to a child with assigned direction \(d\), a turn is counted if and only if \(p \neq 0\), \(d \neq 0\) and \(p \times d < 0\) (i.e. the sign changes). Otherwise no turn is counted. In other words, continuing in a non‐changing direction (or starting from the root) does not incur any turn cost.

You are given an integer \(k\). A snail path is valid if the total number of turns along the entire path from the root to the leaf does not exceed \(k\). Note that the unique path from the root to any node has an associated turn count (accumulated as above).

You will be given \(q\) queries. In each query a node \(u\) is specified. For each query, compute the number of leaf nodes \(v\) such that there exists a valid snail path from the root to \(v\) (i.e. with at most \(k\) turns) that passes through \(u\). In other words, if the unique path from the root to \(u\) has already incurred \(T\) turns and has last direction \(D\), then you need to count the number of leaves in the subtree of \(u\) that are reachable from \(u\) by a path (starting with previous direction \(D\)) using at most \(k - T\) additional turns.

Note on the child ordering and direction: For every node with \(m\) children, label them in the order they appear in the input. The horizontal offset for the \(j\)th child is \(d = j - \lceil m/2 \rceil\). For example, if a node has 2 children then the first child has \(d = 1 - 1 = 0\) and the second child has \(d = 2 - 1 = 1\). When moving from a parent with previous incoming direction \(p\) to a child with offset \(d\):

• If \(p = 0\) (i.e. at the root or just starting), no turn is counted.
• If \(d = 0\) then the move is considered straight (no turn).
• If both \(p\) and \(d\) are nonzero and have opposite signs (i.e. \(p \times d < 0\)), then this move counts as one turn.
• Otherwise, no turn is counted.

You need to answer each query accordingly.

inputFormat

The first line contains three integers \(n\), \(k\), and \(q\) \( (1 \le n \le \text{small},\, k \ge 0,\, q \ge 1) \) — the number of nodes, the maximum number of allowed turns, and the number of queries.

The next \(n-1\) lines describe the tree. For \(i = 2,3,\dots,n\), the \(i\)th node's parent is given by an integer. (The tree is given in the order of node indices, so the order in which children appear for any node is the order in which they are given.)

The next \(q\) lines each contain one integer \(u\) (\(1 \le u \le n\)), representing a query node.

outputFormat

For each query, output a single integer on a new line: the number of leaf nodes \(v\) (in the subtree of \(u\)) such that there exists a valid snail path from the root to \(v\) (with at most \(k\) turns) that passes through \(u\).

sample

5 1 3
1
1
2
2
1
2
3

3
2
1