#P17640. Dream and the Multiverse
Dream and the Multiverse
题目描述
Dream 将时空抽象为一颗 节点有向有根树,其中树根为节点 并且所有边的方向都为浅往深。
Dream 用他的超能力在这颗树上额外添加 条有向边,但最终的图仍然是无环图。
Dream 进而将一个事件抽象为图上的一个节点,将一个时代抽象为图上的一个简单路径。
Dream 认为一对事件 可行 当且仅当存在一个时代,使得时代的首事件是 ,末事件是 。
Dream 现在有 组询问。第 组询问用两个正整数 与 表示,其中 。
Dream 想知道,对每一组询问,有多少对 可行 事件 ,使得 。
输入格式
第一行两个整数 。
接下来一行 个正整数描述树的结构。第 个数代表 号节点的父亲的编号 ,也就是说存在一个 往 的一条边。
接下来 行,每行两个正整数 ,表示一条 往 额外添加的边。
接下来一个正整数 。
接下来 行,每行两个正整数 ,表示一组询问。
输出格式
输出 行,每行一个整数,表示对应组询问的答案。
输入输出样例 #1
输入 #1
2 2
1
1 2
1 2
1
1 2
输出 #1
3
说明/提示
数据规模与约定
本题采用捆绑测试。
- Subtask 1(1 pts):树形成一条链。
- Subtask 2(11 pts):。
- Subtask 3(7 pts):。
- Subtask 4(23 pts):。
- Subtask 5(17 pts):。
- Subtask 6(41 pts):没有特殊限制。
对于 的数据,,,。
保证 额外添加的边不会形成环,给定的 形成一颗根为 的树。
保证 。