P3712 Girls und Panzer

If you are not interested in Shankouding (pinyin) and G&P, you can ignore the background, because you probably won’t understand it anyway.  In the 63rd National High School Sensha-dō Tournament, the war goddess Miho Nishizumi led the Ōarai Girls’ Academy to defeat all other high schools and win the championship, which meant the school would not be shut down. However, a group of Sensha-dō officials said they were just kidding, and the shutdown would still proceed. Miho’s mother, Shiho Nishizumi, scolded the shutdown guy. To avoid making big news, the shutdown guy promised that if Ōarai could defeat the University Team, the school would not be shut down. (It feels like an OI contestant versus an ACM contestant.) But the strength gap was huge. Ōarai’s strongest tank was the Tiger (P), while the University Team fielded all M26 Pershings, M24 Chaffees, plus a T95 that could go 20 and the Karl-Gerät mortar. It felt unwinnable. At this moment, a bald fat man named Sergei • Burkatovsky and a CEO surnamed Wang, who was suffering from cancer and urgently needed money for treatment, came to help them. They gave the Ōarai girls a pile of tank blueprints of dubious authenticity and claimed they were real and historically accurate. The Ōarai Automotive Club was thrilled upon seeing these blueprints and began modding their tanks. Tiger (P) -> Grille 17 Panzer IV Ausf. D -> Panzer IV Waffenträger 38(t) -> Rheinmetall Waffenträger B1-bis -> 105 leFH18B2 Even so, with only 8 tanks, Ōarai still couldn’t defeat the University Team with 30 tanks. According to the script, friends from other high schools were supposed to help, but they were currently studying OI and had stumbled upon a very magical data structure problem. They couldn’t solve it, so they couldn’t come. As a real-world national team member, you can certainly crush a 2D OI problem in seconds. Please help them!

 You are given a rooted tree with $n$ nodes, rooted at $1$, with edge weights, and there are $m$ operations. 1. Query the $k$-th smallest depth value among nodes in the subtree of $x$. If the subtree has fewer than $k$ nodes, output $-1$. 2. Add $k$ to the weight of the edge between $x$ and its parent. It is guaranteed that in every operation 2, the value $k$ and all original edge weights in the tree are less than or equal to a number $len$. If $x$ is $1$ in operation 2, then it is treated as adding $k$ to the base depth of $x$.

 The first line contains three integers $n$, $m$, and $len$. The next $n - 1$ lines each contain two integers, describing for nodes $2$~$n$ the parent of each node and the weight of the edge to its parent. The next $m$ lines each contain three integers $opt$, $x$, and $k$. Here $opt$ denotes the operation type, and $x$, $k$ have the meanings described above.

For each operation of type 1, output a single integer representing the answer.

Constraints and Hints For 10% of the testdata, $n, m \leq 1000$. For 30% of the testdata, $n, m \leq 30000$. For 100% of the testdata, $n, m \leq 100000, len \leq 10$. This easy problem uses bundled testdata. You can only receive the points for a subtask if you pass all testdata in that subtask. If you are not interested in Shankouding (pinyin) and G&P, you can ignore the ending. If you solved this problem: The girls read your STD and all got AC on this problem, then went to help the war goddess. They found 30 “183”s and blasted the enemy in the face. If you didn’t solve this problem: Although the girls really wanted to help the war goddess, they couldn’t. After all, learning Sensha-dō doesn’t grant direct admissions. There was no other way; they had to fight 8 versus 30. The Rheinmetall camped in the bushes. No one on the University Team spotted it. After it destroyed five enemy tanks, its hull couldn’t withstand the gun’s recoil and it fell apart. The StuG III also camped in the bushes. No one on the University Team spotted it, and it didn’t spot anyone either. In the end it couldn’t sit still, charged forward, destroyed a Pershing, and was then destroyed. The Waffenträger reversed artistically. The University Team was dumbfounded when they saw it. After it destroyed eight enemy tanks, its hull couldn’t withstand the gun’s recoil and it fell apart. The Tiger (P) took out the 95 with a single shot, then burned down due to an engine failure during repositioning. Finally, the French B1 fixed bayonets and stabbed 15 of them, turning the game around.  Translated by ChatGPT 5