8867: BZOJ4867:[Ynoi2017]舌尖上的由乃

Memory Limit:256 MB Time Limit:6 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

由乃为了吃到最传统最纯净的美食,决定亲自开垦一片菜园。现有一片空地,由乃已经规划n个地点准备种上蔬菜 。最新鲜的蔬菜需有最甘甜井水的灌溉,因此由乃将要打出两口井,分别记为井A、井B。现在问题来了,由乃可是 一周目的神,为何要打井?是谁想出来的这些题面?由乃不善于搞事情,于是提出以下几个方法,再根据这些方法 找出题人。方法如下: 1. 做完这个出题人出的所有题 2. 做完所有数据结构题 3. 出一道奇怪的数据结构题,而且卡常卡死所有做题的 至于为什么这样能找到出题人呢。。。我也不信她能找到我。。。(能找到岂不是更好?) 因为由乃是神,所有她有很多秒时间,她终于做完了世界上左右的数据结构题 于是该她出题了,她左思右想,出了一个简单数据结构题: 给你一个n个点的有根树,1为根,带边权,有m次操作。 1、求x的子树中第k小的深度的值,如果子树中没有k个点则输出-1; 2、将x与x父亲的边权加上k。 保证每次操作2的k以及原树的边权小于等于一个数len。 如果操作2中x为1,那么视为将x的基础深度加上了k。 由乃能不能找到出题人呢?


输入格式

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


输出格式

对于每个操作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

提示

对于所有数据,n,m <= 100000,len <= 10 因为出题人是sb,len <= 10,其实没有这个限制也可以解决这个问题


题目来源

By 佚名提供

加入题单

上一题 下一题 算法标签: