#P3351. [ioi2009]Regions
[ioi2009]Regions
地区 / Regions
题目描述
联合国区域发展署有 名雇员,按资历从高到低编号为 到 。 号雇员是主席。每名雇员来自 个地区中的一个,地区编号为 到 。除主席外,每名雇员恰有一名资历比自己高的直属上级。
若雇员 是 的直属上级,或 是 的直属上级的上级,则称 是 的上级。沿直属上级关系可以逐级向上,主席是所有其他雇员的上级。
给定组织结构,回答 次询问。每次给定两个不同的地区 ,求有多少个有序雇员对 满足 来自 、 来自 ,且 是 的上级。
输入格式
从标准输入读取。第一行是三个整数 。接下来 行按资历给出雇员信息。第一行是主席的地区 。其余每行有两个整数 ,分别表示雇员 的直属上级编号和所属地区。
接下来 行,每行两个整数 ,表示一次询问。
输出格式
向标准输出写入 行。按询问顺序,每行输出一个整数,表示符合条件的有序雇员对数。
样例 1
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
数据范围
,,,。两地区不同,且每个询问的答案小于 。
| 原赛分值 | 范围 |
|---|---|
| 30 分 | |
| 55 分 | 各地区均不超过 名雇员 |
| 15 分 | 同时满足上述两项 |
| 70 分 | 至少满足上述一项 |