#P11879. [2023年联测]有向图

    ID: 11030 传统题 12000ms 512MiB 尝试: 1 已通过: 1 难度: 9 上传者: 标签>CF2600省选/NOI-位集加速可达性DAG 动态规划Kahn 算法二维前缀和一维前缀和离线查询位计数矩阵转置

[2023年联测]有向图

题目描述

给定一棵以 11 为根的有向外向树,所有树边都从父节点指向子节点。再加入 mm 条有向边,加入后整个图仍然无环。可能出现重边。

有 qq 次询问。每次给定 l,rl,r,求满足 l≤i,j≤rl\le i,j\le r 且 ii 可以到达 jj 的有序点对 (i,j)(i,j) 数量。每个点都可以通过长度为 00 的路径到达自身,重边不重复计数。

输入格式

第一行两个整数 n,mn,m。第二行 n−1n-1 个整数 f2,…,fnf_2,\ldots,f_n,表示每个 i=2,…,ni=2,\ldots,n 有一条树边 fi→if_i\to i。

接下来 mm 行,每行两个整数 u,vu,v,表示加入一条有向边 u→vu\to v。再下一行一个整数 qq,接下来 qq 行各给出两个整数 l,rl,r。

输出格式

每次询问输出一行一个非负整数。

样例 1

2 2
1
1 2
1 2
1
1 2
3

样例 2

8 1
4 7 3 8 2 1 7
1 2
8
1 4
4 8
3 5
1 1
2 5
1 5
1 3
6 7
10
11
4
1
7
12
6
3

原题另外在下发文件中提供样例 3、4。

数据范围

2≤n≤1052\le n\le10^5,0≤m≤1050\le m\le10^5,1≤q≤5×1051\le q\le5\times10^5,1≤fi,u,v≤n1\le f_i,u,v\le n,1≤l≤r≤n1\le l\le r\le n。

子任务 分值 额外限制
1 3 树为一条链
2 14 n,m,q≤1000n,m,q\le1000
3 7 m=0m=0,fif_i 在 [1,i−1][1,i-1] 中随机生成
4 15 m≤5m\le5
5 25 n,m,q≤5×104n,m,q\le5\times10^4
6 16 q≤105q\le10^5
7 20 无

原 PDF 题面