Minimax Tree Stability Attack

A rooted tree is given with nodes numbered from 1 to n. The root is node 1 and has depth 1; every other node’s depth is one more than that of its parent. Some nodes are leaves. Initially, for every leaf with number i the weight is set to i. For every internal (non‐leaf) node, its weight is defined using a minimax rule:

• If the node’s depth is odd, its weight equals the maximum of the weights of its children.
• If the node’s depth is even, its weight equals the minimum of the weights of its children.

Let W be the weight computed at the root with the initial assignment.

Now, an adversary (Cedyks) plans a quantum attack. In an attack, Cedyks obtains control over a nonempty subset S of the leaf nodes. For each leaf node i in S its weight may be reassigned to an arbitrary integer w_i (possibly negative). Changing the weight of leaf i from its original value i to w_i consumes energy |i − w_i|. Since all leaves in S are modified simultaneously, the total energy cost is max_i∈S |i − w_i|. Cedyks wants to disturb the root’s weight—that is, after the modifications the new minimax evaluation of the tree is not equal to W—while spending as little energy as possible. We define the stability w(S) of a leaf set S as the minimum energy needed (over all valid reassignments on leaves in S) to change the root’s weight. In some cases, no matter how one changes the weights of the leaves in S the root’s value will remain W; in those cases, we define w(S) = n (where n is the number of nodes in the tree).

Cedyks is interested in the following: if the tree has m leaves then there are 2^m − 1 nonempty subsets of leaves. Given an interval [L, R], for every integer k in this interval, determine how many subsets S have stability w(S) = k.

Note on the minimax evaluation: When reassigning weights, only the leaves in S may have their values changed (within the constraint that the new value for a leaf i must lie in the interval [i − E, i + E] if spending energy E). All other leaves remain fixed at their initial value (which is equal to the leaf’s index). The effect then propagates upward:

• At a leaf which is controlled the attainable range is [i − E, i + E]; if not controlled, its value is fixed at i.
• An internal node at odd depth (a max‐node) obtains a value equal to the maximum of the values (or attainable ranges) of its children. In effect, if the children’s attainable ranges are intervals, then the node’s attainable range is the interval from the maximum of the children’s lower bounds to the maximum of their upper bounds.
• Similarly, at an internal node at even depth (a min‐node) the attainable range is from the minimum of the children’s lower bounds to the minimum of their upper bounds.

Since only one controlled leaf may need to be modified while the others can be left unchanged, one may show that the minimal energy required when controlling a set S is the minimum, over leaves i in S, of the energy required if only i is controlled. For a leaf i, consider its unique path from the root. At each internal node along the path that has other (fixed) children, one can compute a candidate required energy. For a max‐node (at odd depth) with sibling values (fixed) having maximum c, one candidate is max(0, i − (c − 1)) (since one must lower the contribution from the controlled branch below c). Similarly, for a min‐node (even depth) with sibling value c, the candidate is max(0, (c + 1) − i). The minimum over all such candidates (if any exist) is the energy needed by leaf i; if no candidate exists then controlling that leaf cannot change the root’s value and we set its required energy to n.

Thus, if for each leaf we define f(i) as the minimum energy required (if controllable) and take it to be n if not, then for any nonempty set S the stability is

w(S) = min { f(i) : i ∈ S }.

Finally, given the tree (described by its structure) and an interval [L, R], output for each k in [L, R] the number of nonempty leaf subsets S for which w(S) = k.

inputFormat

The input begins with an integer n (the number of nodes). The nodes are numbered 1 through n, with node 1 as the root. Then follow n−1 integers, where the i‑th integer (for i = 2, …, n) is the parent of node i (this defines the tree).

The next line contains two integers L and R representing the query interval.

Note: The leaves are those nodes with no children. For each leaf node i, its initial weight is i.

outputFormat

Output R − L + 1 space‐separated integers. The k-th integer (starting from k = L to R) should equal the number of nonempty leaf subsets S for which the stability w(S) equals that value.

sample

3
1 1
0 3

2 0 1 0