Interactive Tree Reconstruction

In this problem, you are given a rooted tree with \(n\) nodes where node 1 is the root. Each edge of the tree is assigned a unique weight from \(1\) to \(n-1\) (in \(\LaTeX\) format). You need to reconstruct the tree by determining the parent of each node and the initial weight of the edge connecting the node to its parent. To achieve this, you are allowed to perform two kinds of operations via an interactive library:

• Exchange Operation: Given two distinct integers \(x\) and \(y\) with \(1 \le x, y < n\), swap the weights of the two edges that currently have these weights.
• Query Operation: Given an integer \(u\) with \(2 \le u \le n\), return the maximum weight among all edges on the unique path from the root (node 1) to node \(u\).

Your task is to use these operations to extract the tree structure and the initial edge weights. Once you have determined these, call the provided answer function exactly once with two arrays:

• par: an array of length \(n-1\) where par[i] represents the parent of node \(i+2\).
• val: an array of length \(n-1\) where val[i] represents the initial weight of the edge connecting node \(i+2\) to its parent.

Implementation Details:

#include "ds.h"

void solve(int n, int lim1, int lim2);

// You may call the following functions to interact with the judge:

// Exchange operation: swap the weights of the two edges that currently have weights x and y
void exchange(int x, int y);

// Query operation: returns the maximum weight on the path from the root (node 1) to node u
int query(int u);

// Answer function: used to output your reconstructed tree
void answer(std::vector par, std::vector val);

Note that the tree structure and the initial edge weights are fixed from the beginning and do not change with your operations. You must not call the answer function more than once.

inputFormat

The input is provided via standard input with the following format:

1. The first line contains three positive integers \(n\), \(lim1\), and \(lim2\), where \(n\) is the number of nodes, \(lim1\) is the limit on the number of exchange operations, and \(lim2\) is the limit on the number of query operations.
2. The second line contains \(n-1\) positive integers: \(p_2, p_3, \dots, p_n\). Here, \(p_i\) denotes the parent of node \(i\) in the tree.
3. The third line contains \(n-1\) positive integers: \(v_2, v_3, \dots, v_n\). These represent the initial weights on the edges, and they form a permutation of \(\{1, 2, \dots, n-1\}\).

outputFormat

You do not output anything to standard output directly. Instead, once you have deduced the tree structure and the initial edge weights, you must call the provided answer function exactly once with two arrays:

• par: An array of length \(n-1\), where par[i] should be the parent of node \(i+2\).
• val: An array of length \(n-1\), where val[i] should be the initial weight of the edge connecting node \(i+2</code> to its parent.

The interactive grader will compare your provided arrays with the correct tree. If they match, it will output a message indicating the number of exchange and query calls as follows:

Right output! cnt1 = A, cnt2 = B.

where \(A\) and \(B\) are the counts of exchange and query operations performed, respectively.

sample

3 0 0
1 1
1 2

Right output! cnt1 = 0, cnt2 = 0.