Problem : 270 - Regions

Problem Statistics

Solved Member: 7　　Submission: 56　　User Tried: 7

Statement:

聯合國區域發展局(UNRDA)有一個定義明確的組織結構。該局總共聘用了N位職員，每一位分別來自世界上R個不同的區域(每個區域的代號是 1 至 R ，但並無任何特別順序)。職員依年資從 1 編號到 N，編號 1 職員的頭銜為主任(Chair)，也是最資深的職員。除了主任之外，每一位職員都有一位小老闆(direct supervisor)，小老闆一定比該職員資深。

我們定義職員 A 為職員 B 的上司(manager)唯若且若 A 是 B的小老闆或 A 是 B的小老闆的上司。因此主任是其他所有職員的上司。此外任兩位職員也不可能相互都是對方的小老闆。

然而，聯合國調查局(UNBI)最近接到一些檢舉：UNRDA的內部組織並不平衡，某些區域比其他區域更獲得重視。為了調查這些檢舉的真實性，UNBI希望發展一個資訊系統，給定UNRDA的管理層級資訊，就可以回答下述問題：給定兩個不同的區域代號 r₁ 與 r₂ ，試問有多少職員組合 (e₁, e₂)滿足職員 e₁ 來自區域 r₁ 、職員 e₂ 來自區域 r₂ ，且 e₁ 是 e₂ 的上司。

Task:

給定每一位職員的區域屬性，以及誰是誰的小老闆的資訊，請寫一個程式來回答問題。

範圍限制：
1 ≤ N ≤ 200000，職員人數。
1 ≤ R ≤ 25000，區域數。
1 ≤ Q ≤ 200000，你的程式所需回答的提問數。
1 ≤ H_k ≤ R，職員 k 的區域屬性 (1 ≤ k ≤ N)。
1 ≤ S_k ≤ k，職員 k 的小老闆編號 (2 ≤ k ≤ N)。
1 ≤ r₁, r₂ ≤ R，每一個提問中的區域代號。

Input:Output:

第一行有三個以空白隔開的正整數N、R和Q。

接下來的N行，依照年資多寡描述N位職員的資訊，這N行中第k行描述職員k的資訊。這些資料的第一行(描述主任的資訊)有單一整數：主任的區域屬性H₁。其餘N-1行，每行兩個以空白隔開的整數：職員k的小老闆S_k與職員k的區域屬性H_k。

接下來有Q行，每行以兩個正整數r₁, r₂表示一個提問。

共輸出Q行，第i行表示第i個提問的答案。

Sample Input:Sample Output:

6 3 4
1
1 2
1 3
2 3
2 3
5 1
1 2
1 3
2 3
3 1

1
3
2
1

Source:

IOI 2009

Problem Setter

hanhan0912

Testdata:

Test	Time	Memory	Score
0	1000ms	131072kb
1	2000ms	131072kb	1
2	2000ms	131072kb	1
3	2000ms	131072kb	1
4	2000ms	131072kb	1
5	2000ms	131072kb	1
6	2000ms	131072kb	1
7	2000ms	131072kb	1
8	2000ms	131072kb	1
9	2000ms	131072kb	1
10	2000ms	131072kb	1
11	2000ms	131072kb	1
12	2000ms	131072kb	1
13	2000ms	131072kb	1
14	2000ms	131072kb	1
15	2000ms	131072kb	1
16	8000ms	131072kb	5
17	8000ms	131072kb	5
18	8000ms	131072kb	5
19	8000ms	131072kb	5
20	8000ms	131072kb	5
21	8000ms	131072kb	5
22	8000ms	131072kb	5
23	8000ms	131072kb	5
24	8000ms	131072kb	5
25	8000ms	131072kb	5
26	8000ms	131072kb	5
27	8000ms	131072kb	5
28	8000ms	131072kb	5
29	8000ms	131072kb	5
30	8000ms	131072kb	5
31	8000ms	131072kb	5
32	8000ms	131072kb	5