#P11879. [2023年联测]有向图
[2023年联测]有向图
题目描述
给定一棵以 为根的有向外向树,所有树边都从父节点指向子节点。再加入 条有向边,加入后整个图仍然无环。可能出现重边。
有 次询问。每次给定 ,求满足 且 可以到达 的有序点对 数量。每个点都可以通过长度为 的路径到达自身,重边不重复计数。
输入格式
第一行两个整数 。第二行 个整数 ,表示每个 有一条树边 。
接下来 行,每行两个整数 ,表示加入一条有向边 。再下一行一个整数 ,接下来 行各给出两个整数 。
输出格式
每次询问输出一行一个非负整数。
样例 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。
数据范围
,,,,。
| 子任务 | 分值 | 额外限制 |
|---|---|---|
| 1 | 3 | 树为一条链 |
| 2 | 14 | |
| 3 | 7 | , 在 中随机生成 |
| 4 | 15 | |
| 5 | 25 | |
| 6 | 16 | |
| 7 | 20 | 无 |