Merge Information on Trees

We are given a rooted tree (T=(V,E)) with (n) nodes (numbered (1,2,\ldots,n)) and a set of information objects (I) with two special elements: the unit (\epsilon) and the illegal information (\bot). For each edge (e=(u,v)) in (E) there is an associated information element (\iota(e)) with point set (S_V(\iota(e)) = {u,v}) and edge set (S_E(\iota(e))={e}). Information objects (other than (\epsilon) and (\bot)) have two attributes: a two‐element point set and an edge set (which is a subset of (E)); the unit has an empty edge set and the illegal information has neither attribute.

There are two merge operations defined on (I): for all (a,b\in I) let \n(r = R(a,b)) and (c = C(a,b)). They satisfy the following rules:

1. Merging with the unit: if (a=\epsilon) then (R(a,b)=C(a,b)=b); similarly if (b=\epsilon) then the result is (a).
2. Merging with (\bot): if one of (a) or (b) is (\bot), then (R(a,b)=C(a,b)=\bot).
3. Otherwise, if (S_E(a) \cap S_E(b) \neq \varnothing) or (|S_V(a)\cap S_V(b)| \neq 1), then the merge results in (\bot).
4. Otherwise, we have [ S_E(r)=S_E(c)=S_E(a)\cup S_E(b), \quad S_V(r)=S_V(a), \quad S_V(c)=S_V(a)\oplus S_V(b), ] where (\oplus) denotes the symmetric difference of sets.

The tree distance between two nodes is defined as the number of edges on the unique simple path between them. You are given a scoring parameter (M) and (q) queries. Each query provides a node (u) and a nonnegative integer (d). Let (X) be the set of nodes at distance at most (d) from (u) in (T) and let (Y) be the set of edges with both endpoints in (X). It can be proven that starting from (\epsilon) and all (\iota(e)) ((e\in E)) one can perform a sequence of calls to (R) and (C) (with a total count not exceeding (M)) to obtain a (nonillegal) information object (o) such that (S_E(o)=Y).

In particular, if (d=0) you should simply return (\epsilon).

In this problem you must implement the following functions (do not write a main function):

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

• info ask(int u, int d);

== Implementation details ==

Your program must include the header file

#include "count.h"

The header file defines the type (info), the constant (emptyinfo) (corresponding to (\epsilon)), the merge functions:

info MR(info a, info b);  // returns R(a,b)
info MC(info a, info b);  // returns C(a,b)

and the function

bool isempty(info a);   // returns true if and only if a is the unit \(\epsilon\)

Merge calls must always result in a valid information object (i.e. never (\bot)).

== Interaction and Testing ==

The testing library will call init exactly once and then ask exactly (q) times. In each query you are given the parameters (u) and (d) as described above. Your returned information must satisfy (S_E(o)=Y) for the set (Y) defined by the query.

The input format for the testing program is as follows:

• First line: four integers (id, n, q, M).
• Second line: (n-1) integers (p_2, p_3, \ldots, p_n) with (p_i < i) indicating the parent of node (i) in (T).
• Next (q) lines: two integers (u, d) per line describing a query.

The output of your program (when linked with the grading libraries) will be three integers representing the merging call counts as described in the problem statement.

Your solution must build an appropriate merge sequence based on the induced subgraph (ball) of (T) for each query.

inputFormat

The input consists of multiple integers. The first line contains four integers (id, n, q, M). The second line contains (n-1) integers (p_2, p_3, \ldots, p_n) where (p_i < i) is the parent of node (i) in (T). This is followed by (q) lines, each containing two integers (u) and (d) representing a query.

outputFormat

Your solution does not need to print any output on its own. Instead, you must implement the functions init and ask as described. During testing, the interactive library will call these functions and check that the final merged information for each query satisfies (S_E(o)=Y) (and (o \neq \bot)).

sample

1 5 3 100
1 1 2 2
1 1
2 2
3 1

0 0 0