6500: BZOJ2500：幸福的道路

小T与小L终于决定走在一起,他们不想浪费在一起的每一分每一秒,所以他们决定每天早上一同晨练来享受在一起的时光. 他们画出了晨练路线的草图,眼尖的小T发现可以用树来描绘这个草图. 他们不愿枯燥的每天从同一个地方开始他们的锻炼,所以他们准备给起点标号后顺序地从每个起点开始(第一天从起点一开始,第二天从起点二开始……). 而且他们给每条道路定上一个幸福的值.很显然他们每次出发都想走幸福值和最长的路线(即从起点到树上的某一点路径中最长的一条). 他们不愿再经历之前的大起大落,所以决定连续几天的幸福值波动不能超过M(即一段连续的区间并且区间的最大值最小值之差不超过M).他们想知道要是这样的话他们最多能连续锻炼多少天(hint:不一定从第一天一直开始连续锻炼)? 现在，他们把这个艰巨的任务交给你了!

输入格式

第一行包含两个整数N, M(M<=10^9). 第二至第N行,每行两个数字Fi , Di, 第i行表示第i个节点的父亲是Fi,且道路的幸福值是Di.

输出格式

最长的连续锻炼天数

样例输入

3 2
1 1
1 3

样例输出

3
数据范围：
50%的数据N<=1000
80%的数据N<=100 000
100%的数据N<=1000 000
 

提示

没有写明提示

题目来源

没有写明来源