Person in Charge

• 035966_L3

Attention

The sample cases for this problem are not located in subtask 0. Instead, they are placed elsewhere:

Sample 1 will be judged three times.

Subtask dependencies are as follows:

File I/O is required (garbage.in / garbage.out).

In this problem, two cleanup sequences $\bm{\{a_i\}}$ and $\bm{\{b_j\}}$ are considered essentially different if and only if at least one of the following holds:

• $i \ne j$, or
• there exists $\bm{1 \le k \le \min\{i, j\}}$ such that $\bm{a_k \ne b_k}$.

Problem Background

Sleeping Goose is the chief administrator of the garbage stations in the Kingdom of Sleeping Cup.

In recent years, as the number of garbage stations keeps increasing, Sleeping Goose feels more and more overwhelmed.

To better manage the kingdom’s garbage stations, it has hired some employees.

Unfortunately, these employees are often derelict in their duties…

Problem Description

The Kingdom of Sleeping Cup has $n$ garbage stations.

• Station $1$ is the central station.
• Stations $2, 3, \ldots, n$ are branch stations.
  Each branch station has exactly one direct superior station whose number is strictly smaller than itself.

This morning, Sleeping Goose checked the surveillance of all stations, counted the number of garbage bags currently stored at each station (all positive integers not exceeding $n$), and decided to let its employees perform a major cleanup.

According to the on-the-job training, Sleeping Goose must provide an operation sequence $\{c_k\}$ with $1 \le c_i \le n$, and the employees will, in ascending order $i = 1, 2, \ldots, k$, perform the following for each $i$:

• If $c_i = 1$, do nothing.
• Otherwise, transport all garbage from station $c_i$ to its direct superior station.

After the employees finish, all garbage in station $1$ will be taken away by Sleeping Goose itself to the waste treatment plant.

Unfortunately, as mentioned in the background, the employees are very lazy. Specifically, they will actually execute the following lazy version of the procedure:

• If $c_i = 1$, do nothing.
• If station $c_i$ currently contains $\le i$ bags, do nothing.
• Otherwise, leave exactly $i$ bags in station $c_i$ and transport the remaining bags to its direct superior station.

Nevertheless, Sleeping Goose still wants to maximize the amount of garbage cleaned up while using the shortest possible sequence of operations.

To help Sleeping Goose, you need to answer three questions:

1. What is the maximum number of garbage bags that can be cleaned up in this cleanup?
2. Under the condition that the amount cleaned is maximized, what is the minimum length of the operation sequence?
3. Under the above two conditions (maximum bags cleaned and shortest sequence), how many essentially different cleanup plans are available?

• The answer to the first question is not taken modulo.
• The answer to the second question is not taken modulo.
• The answer to the third question is modulo $10^9+7$.

Input Format

Multiple test cases.
First line: an integer $T$, the number of test cases.

For each test case:
$n$ lines, each containing two positive integers $f_i,a_i$:

• $f_i$ — the direct superior station of station $i$ (for $i \ge 2$, $1 \le f_i \le i − 1$).
• $a_i$ — the number of garbage bags currently stored at station $i$ ($1 \le a_i \le n$).

Special note: For $i = 1$, the line actually contains $n$ and $a_1$ (i.e., the first line’s two integers are $n$ and $a_1$).

Output Format

For each test case, output one line with three integers:

1. The answer to the first question (no modulo).
2. The answer to the second question (no modulo).
3. The answer to the third question (modulo $10^9+7$).

Samples

2
1 1
2 1
1 1

1 0 1
1 0 1

2
6 6
1 2
1 2
2 3
2 3
2 3
13 10
1 1
2 2
3 3
2 4
3 2
4 3
3 4
4 5
5 3
4 4
5 5
6 6

8 2 3
14 3 1

Sample 2 Explanation

For the first test case, the three optimal cleanup plans are:

• Clean one of stations $4$, $5$, or $6$ ($3$ choices), transporting $2$ bags and leaving $1$ bag behind, so station $2$ has $4$ bags.
• Clean station $2$, transporting $2$ bags and leaving $2$ bags behind, so station $1$ has $8$ bags.

The three operation sequences are: $\{4, 2\}, \{5, 2\}, \{6, 2\}$.

Note that the following six sequences, though they achieve the maximum bags cleaned, do not satisfy the shortest-sequence requirement, hence they are not counted in the answer to the third question:

• After choosing one of $4$, $5$, $6$ and cleaning it ($3$ choices), leaving $1$ bag, station $2$ has $4$ bags.
• Then choose another of the remaining two ($2$ choices), leaving $2$ bags, station $2$ has $5$ bags.
• Finally clean station $2$, transporting $2$ bags, leaving $3$ bags, station $1$ has $8$ bags.

For the second test case, the only optimal sequence is $\{12, 5, 2\}$.

Data Range

For $100\%$ of the data: $1 \le T \le 20$, $1 \le n \le 1000$.

There are four equally-weighted subtasks:

1. Guaranteed $a_i = 1$ for all $i$.
2. Guaranteed $f_i = i − 1$ for all $i \ge 2$.
3. Guaranteed $f_i = 1$ for all $i \ge 2$.
4. No additional constraints.