The United Nations Regional Development Agency (UNRDA)
has a very well defined
organizational structure. It employs a total of N people, each of
them coming from one of R
geographically distinct regions of the world. The employees are numbered from 1
to N inclusive
in order of seniority, with employee number 1, the Chair, being the most senior.
The regions are
numbered from 1 to R inclusive in no particular order. Every
employee except for the Chair has a
single supervisor. A supervisor is always more senior than the employees he or
she supervises.
We say that an employee A is a manager of employee B
if and only if A is B’s supervisor or A
is
a manager of B’s supervisor. Thus, for example, the Chair is a
manager of every other
employee. Also, clearly no two employees can be each other’s managers.
Unfortunately, the United Nations Bureau of Investigations (UNBI) recently
received a number of
complaints that the UNRDA has an imbalanced organizational structure that favors
some regions
of the world more than others. In order to investigate the accusations, the UNBI
would like to
build a computer system that would be given the supervision structure of the
UNRDA and would
then be able to answer queries of the form: given two possibly same regions r1
and r2, how many pairs
of employees e1 and e2 exist
in the agency, such that employee e1 comes from region
r1,
employee e2 comes from region r2,
and e1 is a manager of e2.
Every query has two parameters:
the regions r1 and r2;
and its result is a single integer: the number of different pairs e1
and e2 that
satisfy the above-mentioned conditions.
| 1 <= N <= 200,000 1 <= R <= 25,000 1 <= Q <= 200,000 1 <= Hk <= R 1 <= Sk < k 1 <= r1, r2 <= R |
The number of employees The number of regions The number of queries your program will have to answer The home region of employee k (for 1 <= k <= N) The supervisor of employee k (for 2 <= k <= N) The regions inquired about in a given query |
There are multiple test cases in the input file. For each test case:
Your program must read from standard input the following data:
• The first line contains the integers N, R and
Q, in order, separated by single spaces.
• The next N lines describe the N employees of the agency in order
of seniority. The kth of these N lines
describes employee number k. The first of these lines (i.e., the
one describing the Chair) contains a single integer: the home region H1
of the Chair. Each of the other N-1 lines contains two integers
separated by a single space: employee k’s supervisor Sk,
and employee k’s home region Hk.
Then there are Q queries each is in the form described in the description.
For each query please answer the number of pairs meet the condition above in a line.
6 3 4 1 1 2 1 3 2 3 2 3 5 1 1 2 1 3 2 3 3 1 3 2 1 1 1 2 1 1 1 2
1 3 2 1 1
Migrated from old NTUJ.
ioi2009
| No. | Testdata Range | Score |
|---|