409180: GYM103449 H Autumn
Description
De te-ndeamnă, de te cheamă;
Ce e val, ca valul trece,
Nu spera și nu ai teamă;
Te întreabă și socoate
Ce e rău și ce e bine;
Toate-s vechi și nouă toate:
Vreme trece, vreme vine.
— Mihai Eminescu, GlossăReminiscing sadly on the prispă, El Capoc remembers the autumn. And with the autumn, he remembers a problem that made him very sad at the time:
Given a tree (undirected acyclic graph), rooted in node 1; Let p be the parent of u (i.e. if we were to list the nodes on the path from the root to u, then the second-to-last element would be considered the father of u). Consider that p[1]=1.
Tolerate the following operations:
Update: Given u, the edge between $$$(p,u)$$$ is erased and $$$(p[p],u)$$$ is inserted (i.e. the parent of leaf $$$u$$$ becomes $$$p[p]$$$)
Query: Given u, Determine the maximum distance from u to one of the leaves in it's subtree (i.e. it's height)
InputOn the first line of input, you are given $$$N$$$ and $$$Q$$$ ($$$1 \le N \le 90\,000$$$, $$$1 \le Q \le 190\, 000$$$), the number of nodes, respectively the number of operations. Then, on the following line, $$$N-1$$$ numbers follow, the i-th of with represents $$$p[i+1]$$$. Then, $$$Q$$$ lines follow, on each of these there will be two numbers: $$$t_i$$$ and $$$u_i$$$. If $$$t_i = 1$$$, then you must update the leaf $$$u_i$$$. Otherwise ($$$t_i = 2$$$), print the answer for the query with parameter $$$u_i$$$
OutputFor each query, print the respective distance
Scoring- For 10 points (Group 1), $$$1 \le N \le 1000$$$, $$$1 \le Q \le 2000$$$
- For Another 20 points (Group 2), $$$1 \le N \le 15\,000$$$, $$$1 \le Q \le 30\,000$$$
- For Another 30 points (Group 3), $$$1 \le N \le 22\,500$$$, $$$1 \le Q \le 39\,000$$$
- For Another 40 points (Group 4), consider the initial restrictions
12 18 1 1 1 4 5 6 6 3 2 2 2 1 8 1 8 1 8 2 4 1 7 1 7 1 7 2 4 1 9 1 10 1 11 1 12 2 3 2 2 1 6 2 4 1 5 2 4Output
3 2 0 0 1 1Note
You can find the more clear and animated version of this at https://ibb.co/NW2fwD6 Also, we're terribly sorry for the weird restrictions.