Messages on a Tree

题意翻译

有一棵编号为$0$~$n$的树，$0$为根节点 在一些时刻，某一些节点会向根节点发送信息并开始等待收到根节点的回复，**这些节点被称作发送者**，向根节点发送信息的过程是将信息沿着父节点不断向上传递，**经过的节点都将开始等待根节点的回复**，根节点收到信息后立刻回复，回复的过程是逆着刚才的路径向下传递直至传递回发送信息的节点。 但在这一过程中，如果向上传递信息时遇到的某一个节点本身正在等待根节点的回复，那么这个节点会拒绝向上传递并直接向下回复一个终止的信息，这一向下的过程与从根节点向下回复的过程相同。 父子节点之间传递信息的过程需要花费$1$单位时间 如果一个节点同时收到了很多来自子节点的信息，那么这个节点只处理来自编号最小的**发送者**（不是子节点！！！），然后拒绝剩余的所有信息 如果一个节点同时收到了来自子节点的信息和来自父节点的回复，那么向下传递回复和向上传递信息的过程可以同时进行 如果一个节点在等待的过程中自己成为了发送者，那么这条信息被立刻拒绝，所用时间是$0$ **输入格式：** 第一行两个整数$n$,$m$，表示节点编号和发送信息次数 接下来一行$n$个整数，第$i$个整数表示节点$i$的父节点 接下来$m$行，每行两个整数，分别表示信息的发送者的编号和发送的时刻，保证给出的时刻单调不降 **输出格式：** 一行$m$个整数，表示每次发送信息收到回复的**时间点**

题目描述

Alice and Bob are well-known for sending messages to each other. This time you have a rooted tree with Bob standing in the root node and copies of Alice standing in each of the other vertices. The root node has number $ 0 $ , the rest are numbered $ 1 $ through $ n $ . At some moments of time some copies of Alice want to send a message to Bob and receive an answer. We will call this copy the initiator. The process of sending a message contains several steps: - The initiator sends the message to the person standing in the parent node and begins waiting for the answer. - When some copy of Alice receives a message from some of her children nodes, she sends the message to the person standing in the parent node and begins waiting for the answer. - When Bob receives a message from some of his child nodes, he immediately sends the answer to the child node where the message came from. - When some copy of Alice (except for initiator) receives an answer she is waiting for, she immediately sends it to the child vertex where the message came from. - When the initiator receives the answer she is waiting for, she doesn't send it to anybody. - There is a special case: a copy of Alice can't wait for two answers at the same time, so if some copy of Alice receives a message from her child node while she already waits for some answer, she rejects the message and sends a message saying this back to the child node where the message came from. Then the copy of Alice in the child vertex processes this answer as if it was from Bob. - The process of sending a message to a parent node or to a child node is instant but a receiver (a parent or a child) gets a message after $ 1 $ second. If some copy of Alice receives several messages from child nodes at the same moment while she isn't waiting for an answer, she processes the message from the initiator with the smallest number and rejects all the rest. If some copy of Alice receives messages from children nodes and also receives the answer she is waiting for at the same instant, then Alice first processes the answer, then immediately continue as normal with the incoming messages. You are given the moments of time when some copy of Alice becomes the initiator and sends a message to Bob. For each message, find the moment of time when the answer (either from Bob or some copy of Alice) will be received by the initiator. You can assume that if Alice wants to send a message (i.e. become the initiator) while waiting for some answer, she immediately rejects the message and receives an answer from herself in no time.

输入输出格式

输入格式

The first line of input contains two integers $ n $ and $ m $ ( $ 1<=n,m<=200000 $ ) — the number of nodes with Alices and the number of messages. Second line contains $ n $ integers $ p_{1},p_{2},...,p_{n} $ ( $ 0<=p_{i}&lt;i $ ). The integer $ p_{i} $ is the number of the parent node of node $ i $ . The next $ m $ lines describe the messages. The $ i $ -th of them contains two integers $ x_{i} $ and $ t_{i} $ ( $ 1<=x_{i}<=n $ , $ 1<=t_{i}<=10^{9} $ ) — the number of the vertex of the initiator of the $ i $ -th message and the time of the initiation (in seconds). The messages are given in order of increasing initiation time (i.e. $ t_{i+1}>=t_{i} $ holds for $ 1<=i&lt;m $ ). The pairs $ (x_{i},t_{i}) $ are distinct.

输出格式

Print $ m $ integers — the $ i $ -th of them is the moment of time when the answer for the $ i $ -th message will be received by the initiator.

输入输出样例

输入样例 #1

6 3
0 1 2 3 2 5
4 6
6 9
5 11

输出样例 #1

14 13 11 

输入样例 #2

3 2
0 1 1
2 1
3 1

输出样例 #2

5 3 

输入样例 #3

8 3
0 1 1 2 3 3 4 5
6 1
8 2
4 5

输出样例 #3

7 6 11 

说明

In the first example the first message is initiated at the moment $ 6 $ , reaches Bob at the moment $ 10 $ , and the answer reaches the initiator at the moment $ 14 $ . The second message reaches vertex $ 2 $ at the moment $ 11 $ . At this moment the copy of Alice in this vertex is still waiting for the answer for the first message, so she rejects the second message. The answer reaches the initiator at the moment $ 13 $ . The third message is not sent at all, because at the moment $ 11 $ Alice in vertex $ 5 $ is waiting for the answer for the second message. In the second example the first message reaches Bob, the second is rejected by Alice in vertex $ 1 $ . This is because the message with smaller initiator number has the priority. In the third example the first and the third messages reach Bob, while the second message is rejected by Alice in vertex $ 3 $ .