#P15813. [2025年山东集训第三轮]哩哩哩啦哩啦

    ID: 15024 传统题 2000ms 512MiB 尝试: 1 已通过: 1 难度: 6 上传者: 标签>图论搜索DFS算法基础二分贪心CF1900

[2025年山东集训第三轮]哩哩哩啦哩啦

题目描述

某池塘共有 nn 只青蛙,每只青蛙都有一个唯一的编号,编号从 11 到 nn。编号为 11 的青蛙是池塘总呱呱,除了总呱呱之外,每只青蛙都有一个直接妈妈,青蛙 ii 的直接妈妈编号为 pip_i,且有 pi<ip_i < i。

若 px=yp_x = y,则青蛙 xx 被称为青蛙 yy 的第 11 层蝌蚪;若青蛙 pxp_x 是青蛙 yy 的第 k−1k-1 层蝌蚪,则青蛙 xx 被称为青蛙 yy 的第 kk 层蝌蚪。

现在,公司总呱呱可以选择一些青蛙参加火锅。他决定选择两个数字 LL 和 RR,将所有编号满足 L≤i≤RL \leq i \leq R 的青蛙送去火锅。

在确定 LL 和 RR 之前,总呱呱收到了 mm 条青蛙的要求,第 jj 条要求用两个数字 uju_j 和 kjk_j 表示,这代表青蛙 uju_j 希望其第 kjk_j 层蝌蚪中至少有一只被送去火锅。为了节省费用,总呱呱希望确定 LL 和 RR 的值使得送去培训的青蛙蛙数最少,并且所有青蛙的要求都能满足。

需要编写程序,根据池塘内部的母子级关系和青蛙的要求,找出一对 LL 和 RR,使得所有要求都能得到满足,并且送去火锅的青蛙蛙数最少。如果有多个满足条件的 (L,R)(L, R) 对,选择其中 LL 最小的那个。

输入格式

第一行输入一个整数 nn,表示池塘青蛙的总数(2≤n≤2000002 \leq n \leq 200000)。

第二行输入 n−1n-1 个整数 p2,p3,…,pnp_2, p_3, \dots, p_n,其中 pip_i 表示青蛙 ii 的直接妈妈编号,且 1≤pi<i1 \leq p_i < i。

第三行输入一个整数 mm,表示青蛙的要求数量。

接下来 mm 行,每行包含两个整数 uju_j 和 kjk_j,表示第 jj 条要求。

输出格式

输出两个整数 LL 和 RR,表示选择的青蛙编号区间。如果存在多个符合条件的 (L,R)(L, R) 对,输出其中 LL 最小的那一对。

输入输出样例 #1

输入 #1

7
1 1 2 2 3 3
3
1 1
3 1
1 2

输出 #1

3 6

说明/提示

样例解释

青蛙编号为 3,4,5,63,4,5,6 的青蛙将被送去火锅。这满足所有要求,因为青蛙 33 是青蛙 11 的第 11 层蝌蚪,青蛙 44 是青蛙 11 的第 22 层蝌蚪,青蛙 66 是青蛙 33 的第 11 层蝌蚪。

数据范围

子任务 分值 2≤n≤2\le n\le 1≤m≤1\le m\le 其它特殊性质
11 1919 5050
22 2525 30003000
33 2121 200000200000 pi=i−1p_i=i-1
44 3535