Maximum Independent Set on Recursively Transformed Binary Trees

We are given a rooted binary tree with n nodes (numbered from 1 to n) in which node 1 is the root. For each node i, let (T_i) denote the subtree rooted at i.

We define an operation (\operatorname{merge}(T_1,T_2)) for two rooted binary trees to be a new binary tree whose root has left subtree (T_1) and right subtree (T_2). This result is unique and always exists.

Now, for any rooted binary tree (T) we define a family of trees (G_x(T)) for positive integers (x) recursively. The definition for (G_1(T)) is as follows: starting from the root of (T), follow the chain of right children until reaching a node that does not have a right child; then set its right child to a (deep) copy of (T). The resulting tree is (G_1(T)). For (x>1) we define

[ G_x(T)=G_1\Big(\operatorname{merge}\big( G_{x-1}(T),, G_{x-1}(T)\big)\Big). ]

For a given query with two integers (x) and (i), consider the tree (G_x(T_i)) and compute the size of its maximum independent set. An independent set of a tree is a set of nodes such that no two nodes in the set are adjacent. Each node has weight 1.

It can be shown that the maximum independent set of a rooted tree can be computed via the following recursive formulas: for each node, let

[ \begin{aligned} f(\text{node},1) &= 1 + f(\text{left child},0) + f(\text{right child},0),\ f(\text{node},0) &= \max{f(\text{left child},0),f(\text{left child},1)} + \max{f(\text{right child},0),f(\text{right child},1)}. \end{aligned} ]

The answer for a tree is (\max{f(\text{root},0),f(\text{root},1)}).

Because the definitions of (G_1(T)) and (G_x(T)) involve duplicating or merging trees, the sizes of these trees can grow very fast. In this problem the trees are small and the parameter (x) in each query is also small so that the operations can be simulated by using deep copies of the tree structure.

Input Format: See below.

Output Format: For each query, output the maximum independent set size on a separate line.

inputFormat

The input begins with an integer n (1 ≤ n ≤ 10), the number of nodes in the original tree. Then follow n lines; the i-th line (1-indexed) contains two integers L and R (0 ≤ L,R ≤ n) representing the left child and right child of node i (0 means there is no such child).

Then an integer q (q ≥ 3) is given, the number of queries. Each of the next q lines contains two integers x and i (1 ≤ x ≤ 5, 1 ≤ i ≤ n) representing a query asking for the maximum independent set size of the tree \(G_x(T_i)\).

outputFormat

For each query, output a single integer — the maximum independent set size of \(G_x(T_i)\).

sample

1
0 0
3
1 1
2 1
3 1

1
3
7

</p>