#P7349. 「MCOI-04」Dream and the Multiverse

「MCOI-04」Dream and the Multiverse

题目背景

Link

I have gone over the scenarios in my head,

and there are 6.96969 billion outcomes, and only one of them -

- do I win.

题目描述

Dream 将时空抽象为一颗 nn 节点有向有根树,其中树根为节点 11 并且所有边的方向都为浅往深。
Dream 用他的超能力在这颗树上额外添加 mm 条有向边,但最终的图仍然是无环图。
Dream 进而将一个事件抽象为图上的一个节点,将一个时代抽象为图上的一个简单路径。
Dream 认为一对事件 (i,j)(i,j) 可行 当且仅当存在一个时代,使得时代的首事件是 ii,末事件是 jj
Dream 现在有 qq 组询问。第 ii 组询问用两个正整数 lil_irir_i 表示,其中 liril_i\le r_i
Dream 想知道,对每一组询问,有多少对 可行 事件 (i,j)(i,j),使得 i,j[l,r]i,j\in[l,r]

输入格式

第一行两个整数 n,mn,m
接下来一行 n1n-1 个正整数描述树的结构。第 ii 个数代表 i+1i+1 号节点的父亲的编号 fif_i,也就是说存在一个 fif_iii 的一条边。
接下来 mm 行,每行两个正整数 u,vu,v,表示一条 uuvv 额外添加的边。
接下来一个正整数 qq
接下来 qq 行,每行两个正整数 l,rl,r,表示一组询问。

输出格式

输出 qq 行,每行一个整数,表示对应组询问的答案。

2 2
1
1 2
1 2
1
1 2
3

提示

数据规模与约定

本题采用捆绑测试。

  • Subtask 1(1 pts):树形成一条链。
  • Subtask 2(11 pts):n,q,m1000n,q,m\le1000
  • Subtask 3(7 pts):m5m\le 5
  • Subtask 4(23 pts):n,q,m5×104n,q,m\le5\times10^4
  • Subtask 5(17 pts):q105q\le 10^5
  • Subtask 6(41 pts):没有特殊限制。

对于 100%100\% 的数据,2n1052\le n\le 10^50m1050\le m\le10^51q1061\le q\le 10^6
保证 额外添加的边不会形成环,给定的 fif_i 形成一颗根为 11 的树。
保证 lrl\le r

说明

Minecraft OI Round 4 C
idea & solution:w33z8kqrqk8zzzx33 check:ClCN