#6046. 「雅礼集训 2017 Day8」爷

内存限制:512 MiB 时间限制:2500 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: 匿名

题目描述

如果你对山口丁和 G&P 没有兴趣,可以无视题目背景,因为你估计看不懂 ……

在第 63 回战车道全国高中生大赛中,军神西住美穗带领大洗女子学院的大家打败了其他所有高中,取得了胜利,当然也就不用废校了。
然而一群战车道的领导表示他们是口胡的,废校还是要废的。

军神的母亲西住志穗怒斥废校男,为了不造个大新闻,废校男承诺如果大洗学院可以打败大学队,就不用废校。
(有种 OI 选手 PK ACM 选手的感觉呀)
然而实力差距太大了,大洗女子学院最强的车是虎式 P 型,而大学队清一色的 M26 潘兴,M24 霞飞(突然发现现在霞飞被砍的好惨),还有能跑到 20 的 T95 和卡尔臼炮,感觉根本没法打呀。
这时候一个光头的胖子谢尔盖 • 布尔卡托夫斯基和一个身患癌症急需钱来治病的王姓 CEO 来帮助她们了。
他们把一堆真实性堪忧的坦克图纸给了大洗学院的妹子们,并说这些图纸是真的,而且还原了历史。
大洗学院汽车部的大家看到了这些图纸后非常高兴,开始膜改她们的战车。
虎式 P 型 -> 蟋蟀 17
四号 D 型 -> 四号坦克武器运载车
38(t) 型 -> 莱茵金属公司武器运载车
B1-bis -> 105leFH18B2
即使这样,只有 8 辆战车的大洗女子学院仍然无法打败有 30 辆战车的大学队。

这时候按照剧本其他高中的小伙伴要来帮忙了,然而她们最近正在学习 OI,碰到了一道很神奇的数据结构题,不会做所以来不了。 你作为一个三次元的国家队选手,当然能秒杀二次元的 OI 题啦。 请帮帮她们吧!

给你一个 n 个点的有根树, 1 为根,带边权,有 m 次操作。

  1. x 的子树中第 k 小的深度的值,如果子树中没有 k 个点则输出 -1
  2. x x 父亲的边权加上 k

保证每次操作 2 的 k 以及原树的边权小于等于一个数 \text{len}

如果操作 2 中 x 1 ,那么视为将 x 的基础深度加上了 k

输入格式

第一行三个数 n m \text{len}
之后 n - 1 行每行两个数表示 2 \sim n 每个点的父亲编号,以及他们到父亲的边权。
之后 m 行每行三个数 \text{opt} x k \text{opt} 表示操作种类, x k 意义如题所述。

输出格式

对于每个操作 1,输出一个数表示答案。

样例

样例输入

3 5 3
1 3
2 3
1 1 3
2 3 3
1 1 3
2 1 2
1 1 3

样例输出

6
9
11

数据范围与提示

对于 10\% 的数据, n, m \leq 1000
对于 30\% 的数据, n, m \leq 30000
对于 100\% 的数据, n, m \leq 100000, \text{len} \leq 10

本水题采用捆绑测试,你只有通过该部分分的所有数据才可以得到该部分分的分数。

如果你对山口丁和 G&P 没有兴趣,可以无视结局。
如果你做出来了这个题
妹子们看了你的 STD 之后都 A 了这个题,然后去帮助军神。
她们找了 30 个 183 射了对面一脸。
如果你没做出来这个题
妹子们虽然很想帮助军神,但是也爱莫能助,毕竟学战车道不能保送。
没有办法,只能 8 打 30 了。
莱茵蹲在草里,大学队没有人发现它,成功击杀五辆敌方坦克后因为车体无法承受火炮后坐力而解体。
三突也蹲在草里,大学队没有人发现它,它也没有发现任何人,最后蹲不住了去突击,击毁一辆潘兴后被击毁。
四运文艺倒车,大学队看到之后目瞪口呆,成功击杀八辆敌方坦克后因为车体无法承受火炮后坐力而解体。
虎 P 炮一发带走了 95,然后因为转场的时候发动机故障而烧毁。
最后法五金刺刀了 15 个,成功翻盘。