Subtree Capacity

题目描述

You are given a rooted tree with $n$ vertices, rooted at vertex $1$. Vertex $i$ has a non-negative integer capacity $a_i$.

You may choose a set $S$ of vertices (any subset of the vertices). The set $S$ is called valid if, for every vertex $i$ of the tree, the number of chosen vertices lying in the subtree of $i$ is at most $a_i$:

$$|S \cap \mathrm{subtree}(i)| \le a_i \qquad \text{for all } i = 1, 2, \dots, n,$$

where $\mathrm{subtree}(i)$ is the subtree rooted at $i$ (including $i$ itself).

You must answer $q$ queries. Each query gives two integers $l$ and $r$. For this query, you may only choose vertices whose index lies in $[l, r]$, i.e. $S \subseteq \{l, l+1, \dots, r\}$; however, the capacity constraint above still applies to every vertex of the tree. Report the maximum possible size $|S|$ of a valid set.

Note. The capacity constraint holds for all $n$ vertices, not only for the vertices with index in $[l, r]$. In particular, a vertex $u \notin [l, r]$ (such as a common ancestor or the root) still limits how many chosen vertices its subtree may contain.

输入格式

The first line contains two integers $n$ and $q$.

The second line contains $n$ integers $a_1, a_2, \dots, a_n$.

The third line contains $n-1$ integers $p_2, p_3, \dots, p_n$, where $p_i$ is the parent of vertex $i$.

Each of the next $q$ lines contains two integers $l$ and $r$.

$2 \le n \le 2\cdot10^5$, $1 \le q \le 2\cdot10^5$, $0 \le a_i \le n$, and $1 \le p_i \le n$ where the parents describe a tree rooted at vertex $1$. For each query, $1 \le l \le r \le n$.

输出格式

For each query, output a single line containing the maximum size of a valid chosen set.

样例输入 #1

8 4
4 1 2 1 1 1 1 1
1 1 2 2 3 3 1
1 8
4 8
4 5
6 7

样例输出 #1

4
4
1
2

样例输入 #2

4 2
2 0 1 2
1 1 2
1 4
4 4

样例输出 #2

2
0