Internal Conflicts

We are in the year 338 B.C. Philip II of Macedon, the father of Alexander the Great, is attending the Congress of Corinth, where he leads the effort to establish a federation of Greek states.

Armed with the renowned Macedonian phalanx, he has no doubt about the Greeks' success in the field of battles. If anything concerns him, it is internal disturbances. Before he starts making plans, he wants to know how many pairs of soldiers could potentially engage in a conflict.

The army organization system is as follows:

• There are N soldiers, each identified by a unique natural number between 1 and N.
• Philip has the number ~1~ and has no one directly superior to him.
• Each other soldier u has exactly one immediate superior ~p_u~ (~p_u~ ~\le~ u).

We say that u is "superior" to v if u is equal to v or if u is superior to ~p_v~. If u is superior to v, we also say that v is "inferior" to u. (Note that, with these definitions, a soldier is considered both superior and inferior to himself.) Obviously, Philip is superior to all.

Additionally, each soldier has a strength ~f_u~. Moreover, his strength can be negative, in case his presence in the battle would cause more harm than good.

A soldier's strength is the sum of the strengths of all his inferiors.

Philip, being an experienced general, has observed that the only case in which two soldiers u and v engage in a conflict is:

• If they have exactly equal strength, and furthermore,
• One is not superior to the other.

He assigns his loyal bodyguard, Pausanias of Orestis, a mission. He must report for each soldier the number of soldiers with whom he could potentially engage in a conflict.

Problem:

Develop a program in one of the languages PASCAL, C, C++, Java, which will read the value of N, as well as the values ~p_u~ and ~f_u~ for each member of the army. For each member of the army, it will print the number of soldiers with whom he could potentially engage in a conflict.

Input File:

The input file named conflicts.in is a text file with the following structure. The first line has two integers separated by a space: the total number N of army members and the strength of Philip.

Following are N-1 lines corresponding in order to members u other than Philip (~2 \le~ u ~\le~ N). The i-th line contains two integers separated by a space: the directly superior ~p_{i+1}~ and the strength ~f_{i+1}~ of soldier i+1.

Output File:

The output file named conflicts.out is a text file containing N lines, each with an integer. The i-th line contains the number of army members with whom soldier i could potentially engage in a conflict.

Examples of input - output files:

STDIN (conflicts.in)

10 8
1 -8
1 9
1 -1
3 -3
2 -4
3 -9
5 3
6 5
8 1

STDOUT (conflicts.out)

0
0
1
0
1
3
0
0
0
1

(In the diagram, each circle represents a soldier. The first number is the soldier's number, from ~1~ to ~N~, and the second is his strength.)

Explanation: Let's consider soldier ~5~: He has a strength of ~-3 + 3 + 1 = 1~, just like soldiers ~1~, ~3~, ~6~, ~10~. However, ~1~ and ~3~ are superior to ~5~, and ~10~ is inferior to ~5~. Therefore, the only possible conflict for ~5~ is with soldier ~6~.

Constraints:

• ~1 \le N \le 100.000~
• For each soldier ~u~ other than Philip, it will be ~1 \le p_u < u~.
• For each soldier ~u~, it will be ~-100 \le f_u \le 100~.
• For test cases worth 10%, it will be ~1 \le N \le 1.000~.
• For test cases worth 20%, no soldier will have more than ~50~ superiors.
• For test cases worth 30%, the number of pairs with the same strength will be at most ~2.000.000~.

Attention! Ensure efficient input reading and output printing, especially if you are programming in C++ or Java.

Formatting: In the output, each line terminates with a newline character.
Maximum execution time: 1sec.
Maximum available memory: 64MB.