2690: 云端漫步
题目描述
Nc“打”地鼠的数量远远超过了那位怪蜀黍的想像，所以那位怪蜀黍决定给Nc和kiko最高奖励：飞行能力。Nc和kiko觉得碉堡了，于是Nc和kiko飞上了天空，他们萌生了一个想法：在云端上漫步来享受飞行在天空中的时光。
很快，他们来到了一朵奇葩的云端之上，Nc发现这朵云可以用一个n个端点的树来描述，他们决定每天从这朵云上的不同端点出发（第一天从端点1开始走，第二天从端点2开始走，依次类推），沿着白云之径走到另一个端点为止。Kiko给每条白云之径定上一个幸福的值，很显然他们每次都想走幸福值和最长的路径（即从起点到树上某一点路径最长的一条）。
但是，Nc和kiko不愿意经历大起大落，所以决定连续几天的幸福值和波动不能超过m（即一段连续的区间并且区间的最大最小值的差不超过m），他们想知道要是这样的话他们最多能漫步多少天(即选取【l,r】这段区间满足题意，且使得r-l+1最大）？
输入
第一行两个整数n,m如题所述
接下来第2行到第n行，每行两个整数fi,vi,第i行表示第i个端点的父亲是fi,且白云之径的幸福值为vi
输出
第一行一个整数ans,为最长的漫步天数
样例输入 复制
3 2
1 1
1 3样例输出 复制
3提示
样例输入
样例1：
3 2
1 1
1 3
样例2：
3 2
1 3
2 3
样例输出
样例1
3
样例2
1
样例1说明
第一天从端点1出发，走到3 长度为3
第二天从端点2出发，走到3 长度为4
第三天从端点3出发，走到2 长度为4
于是可以从第一天到第三天一直漫步，最大值4，最小值3，差值为1
样例2说明
第一天从端点1出发，走到3 长度为6
第二天从端点2出发，走到3 长度为3
第三天从端点3出发，走到1 长度为6
于是只能单独选取第一天，或者第二天，或者第三天。
50%的数据 n<=1000
80%的数据 n<=100000
100%的数据 n<=1000000,0<=m<=10^9,0<=vi<=10^6;