Description

小T与小L终于决定走在一起,他们不想浪费在一起的每一分每一秒,所以他们决定每天早上一同晨练来享受在一起的时光.

他们画出了晨练路线的草图,眼尖的小T发现可以用树来描绘这个草图.

他们不愿枯燥的每天从同一个地方开始他们的锻炼,所以他们准备给起点标号后顺序地从每个起点开始(第一天从起点一开始,第二天从起点二开始……). 而且他们给每条道路定上一个幸福的值.很显然他们每次出发都想走幸福值和最长的路线(即从起点到树上的某一点路径中最长的一条).

他们不愿再经历之前的大起大落,所以决定连续几天的幸福值波动不能超过M(即一段连续的区间并且区间的最大值最小值之差不超过M).他们想知道要是这样的话他们最多能连续锻炼多少天(hint:不一定从第一天一直开始连续锻炼)?

现在，他们把这个艰巨的任务交给你了!

Input

第一行包含两个整数N, M(M<=10^9).

第二至第N行,每行两个数字Fi , Di, 第i行表示第i个节点的父亲是Fi,且道路的幸福值是Di.

Output

最长的连续锻炼天数

Sample Input

3 2

1 1

1 3

Sample Output

3

数据范围：

50%的数据N<=1000

80%的数据N<=100 000

100%的数据N<=1000 000

Sol

第一问，每个点能到达的最长链无非就是要么往子树走，要么往父亲走再往上走，那么我们用\(u[i]\)和\(d[i]\)分别表示向上走和向下走的最长链，向下走的直接dfs即可，向上走的我们更新x的儿子的dp值的时候，我们记录x儿子中\(d[i]\)的最大值和次大值，如果这个儿子不是最大值，那么用最大值更新，否则用次大值更新。记得x儿子的初值是\(u[x]\)。

第二问我们开俩单调队列，维护递减的最大值和递增的最小值，加入一个元素的时候按照正常操作更新队列，之后我们要从队首弹出元素直到两者之差小于等于m，弹出队列的过程就是哪边更靠左，就把哪边弹出，然后维护一个pos表示答案能够延伸到的左端点，每次弹出的时候更新为\(q[l1/l2]+1\)。这样经过若干次迭代之后就能找到合法的最靠左的pos，然后用\(i-pos+1\)更新答案。

当然这题的范围是允许st表的，偷懒写st表也可以（模拟赛内存砍了一半所以写不了qwq）

Code

#include 
    
     #define ll long longusing namespace std;struct nod{int t;ll v;nod(int t=0,ll v=0):t(t),v(v){}};vector
     
      e[1000005];int n,x,q1[1000005],q2[1000005],l1=1,l2=1,r1,r2,g=1,ans;ll m,y,u[1000005],d[1000005],a[1000005];void dfs1(int x,int F){for(int i=0,t;i
      
       fm) sm=fm,fm=d[t]+e[x][i].v;        else sm=max(sm,d[t]+e[x][i].v);        u[t]=u[x]+e[x][i].v;    }    for(int i=0,t;i
       
        =a[q2[r2]]) r2--;        q1[++r1]=i;q2[++r2]=i;        while(a[q2[l2]]-a[q1[l1]]>m) if(q2[l2]