P4974 Mystery Passage of the “Poison Tumor”

~~Viston is just a newbie (xiaojuruo) By CYJian (made up by myself)~~. Viston likes adventures the most.

~~(Fake algorithm tags)~~. Viston found a huge castle. He walked in, and there was a huge room inside. Viston went in to look around, and then... he got trapped inside. Viston found that there were many other adventurers in the room and many **passages**. The adventurers rushed into different **passages** one by one, while Viston was totally confused. Using his great “newbie power”, Viston figured out what these **passages** are ~~awesome, right~~. They are one-way **passages**, and these **passages** will teleport you to other rooms. In each room, there is exactly one portal that teleports you to another room. It is known that all rooms eventually lead to one place: the exit. However, being teleported by a portal also takes time. This time depends on how many people have used this portal before, and the formula is $$T=M$$, where $M$ is the number of people who have used the portal. ~~(Why are you spacing out? Everyone else has already left.)~~ Viston remembers how many people entered each passage, and he also detected where the portal in each room leads to. He wants to know: entering the initial room through which passage will let him reach the exit the fastest, ~~because Viston still wants to slack off at McDonald’s~~. ### Note: Only using portals costs time. Passages (i.e., reaching the initial room) cost no time!!!

The first line contains two integers $M$, $N$, where $M$ is the number of rooms (numbered $1-M$), and $N$ is the number of initial passages. In lines $2-------M+1$, each line contains an integer $P$, meaning that room $i$ goes through a portal to room $P$, where node $0$ represents the exit. The testdata guarantees it is a tree. In lines $M+2-------M+N+1$, each line contains two integers $A, B$, meaning this **passage** leads to room $A$, and $B$ people have entered it before. ### Different **passages** may lead to the same room.

Output only one line, $c, d$, where $c$ is the **which** initial room Viston should choose to reach via a passage so that the required time is minimal, and $d$ is the required time. Of course, if multiple initial rooms have the same minimal time, output the initial room that is reached by the passage with the largest index.

## Sample Explanation (Drawn in WindowsXP, sorry if it looks bad.)  For test points 1-5 (10 pts): $1 \leq N, M \leq 50$. For test points 6-10 (20 pts): $1 \leq N, M \leq 5000$. For test points 11-15 (30 pts): $1 \leq N, M \leq 100000$. For test points 16-20 (40 pts): $1 \leq N, M \leq 1000000$. For test points 5, 10, 15, 20, the given tree is generated randomly. It is guaranteed that the answer fits in the range of long long. $\color{white}\text{This way you can see how weak random trees are}$. @[Viston](https://www.luogu.org/space/show?uid=107101) $\color{white}\text{(Still trying to hack tree decomposition.)}$ Translated by ChatGPT 5