Information Merging on Trees

We are given a rooted tree (T=(V,E)) with (n) nodes numbered (1,2,\ldots,n) (with root (1)). In addition, we are provided with a set of informations (I) whose elements have two properties – a point set and an edge set. Two special elements are defined: the unit (or empty) element (\epsilon) and the illegal information (\bot). For any edge (e=(u,v)\in E), an information element (\iota(e)\in I) is given such that

[ S_V(\iota(e)) = {u,v}, \quad S_E(\iota(e)) = {e}. ]

There are two binary merging operations defined on (I): the operations (R) and (C) (invoked as MR and MC in code). They satisfy the following rules:

1. Merging with the unit yields the other information, i.e. if (a=\epsilon) then (R(a,b)=C(a,b)=b).
2. Merging with an illegal information yields (\bot).
3. For two informations (a,b \in I\setminus{\epsilon,\bot}), if (S_E(a)\cap S_E(b)\neq \varnothing) or (|S_V(a)\cap S_V(b)|\neq 1), then \n(R(a,b)=C(a,b)=\bot).
4. Otherwise, we have [ S_E(R(a,b)) = S_E(C(a,b)) = S_E(a) \cup S_E(b), ] [ S_V(R(a,b)) = S_V(a),\quad S_V(C(a,b)) = S_V(a)\oplus S_V(b), ] where (\oplus) denotes the symmetric difference.

The tree distance between two nodes is defined as the number of edges on the unique simple path joining them. You are given a parameter (M) and (q) queries. In each query, a vertex (u) and a nonnegative integer (d) are provided. Let (X) be the set of vertices at tree distance at most (d) from (u) and let (Y = { (a,b) \in E \mid a,b \in X }) be the set of internal edges. It can be proved that starting from (\epsilon) and all the informations (\iota(e)) ((e\in E)) one can, via a finite number of operations (R) and (C), obtain an information (o\neq \bot) such that (S_E(o)=Y).

Your task is to implement the following functions (you do not need to write the main function):

• void init(int T, int n, int q, vector fa, vector e, int M);

• info ask(int u, int d);

In the function init, (fa) is a vector of length (n-1) such that for (0\le i<n-1), the edge (e_i) connects nodes (fa[i]) and (i+2). The corresponding information for that edge is (\iota(e_i)=e[i]). In function ask, you must construct and return an information (o) (via calls to MR and MC) satisfying (S_E(o)=Y) while keeping the total number of MR and MC calls within (M). In particular, if (d=0), simply return the unit information (\epsilon).

It is guaranteed that a valid merging sequence exists. Note that you should include the header file count.h at the beginning of your program. (In our sample implementations, several helper functions are provided in count.h including MR, MC, and isempty.)

Interactive/Testing details: Two different graders (grader.o and checker.o) are used. When linking with grader.o, the program is allowed to output timing information and will not check the correctness of the returned information; however, when linking with checker.o, the returned information will be verified. Be sure not to depend on the specific implementations of the functions in count.h.

Implementation note: You must ensure that the total number of simultaneous info variables is within the memory limits and that the number of MR and MC calls is within the provided limit (M).

inputFormat

The program reads from standard input. The first line contains four integers: (id), (n), (q), (M), representing the test case id, number of nodes, number of queries and the merging call limit respectively. The second line contains (n-1) integers (p_2, p_3, \ldots, p_n) where (p_i < i) is the parent of node (i). Each of the following (q) lines contains two integers (u) and (d) describing a query.

outputFormat

At the end, the interactive library will output three integers (C_1, C_2, C_3) representing the total number of calls to MR and MC in init, in the entire execution, and the maximum number of calls in any single ask, respectively. Your functions should ensure that the returned information for each query satisfies (S_E(o)=Y) as described.

sample

1 3 2 10
1 1
1 0
1 1

5 5 3