#P3351. [ioi2009]Regions

    ID: 2535 传统题 8000ms 128MiB 尝试: 385 已通过: 102 难度: 7 上传者: 标签>难度分类提高+/省选-数据结构根号分治树算法DFS 序子树转区间排序与序列处理差分标记区间修改一维前缀和同向双指针CF2300

[ioi2009]Regions

地区 / Regions

题目描述

联合国区域发展署有 NN 名雇员,按资历从高到低编号为 11 到 NN。11 号雇员是主席。每名雇员来自 RR 个地区中的一个,地区编号为 11 到 RR。除主席外,每名雇员恰有一名资历比自己高的直属上级。

若雇员 AA 是 BB 的直属上级,或 AA 是 BB 的直属上级的上级,则称 AA 是 BB 的上级。沿直属上级关系可以逐级向上,主席是所有其他雇员的上级。

给定组织结构,回答 QQ 次询问。每次给定两个不同的地区 r1,r2r_1,r_2,求有多少个有序雇员对 (e1,e2)(e_1,e_2) 满足 e1e_1 来自 r1r_1、e2e_2 来自 r2r_2,且 e1e_1 是 e2e_2 的上级。

输入格式

从标准输入读取。第一行是三个整数 N,R,QN,R,Q。接下来 NN 行按资历给出雇员信息。第一行是主席的地区 H1H_1。其余每行有两个整数 Sk,HkS_k,H_k,分别表示雇员 kk 的直属上级编号和所属地区。

接下来 QQ 行,每行两个整数 r1,r2r_1,r_2,表示一次询问。

输出格式

向标准输出写入 QQ 行。按询问顺序,每行输出一个整数,表示符合条件的有序雇员对数。

样例 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

数据范围

1≤N,Q≤2000001\le N,Q\le200000,1≤R≤250001\le R\le25000,1≤Sk<k1\le S_k<k,1≤Hk,r1,r2≤R1\le H_k,r_1,r_2\le R。两地区不同,且每个询问的答案小于 10910^9。

原赛分值 范围
30 分 R≤500R\le500
55 分 各地区均不超过 500500 名雇员
15 分 同时满足上述两项
70 分 至少满足上述一项

IOI 2009 原赛题面