Description
小T与小L终于决定走在一起,他们不想浪费在一起的每一分每一秒,所以他们决定每天早上一同晨练来享受在一起的时光.
他们画出了晨练路线的草图,眼尖的小T发现可以用树来描绘这个草图.
他们不愿枯燥的每天从同一个地方开始他们的锻炼,所以他们准备给起点标号后顺序地从每个起点开始(第一天从起点一开始,第二天从起点二开始……). 而且他们给每条道路定上一个幸福的值.很显然他们每次出发都想走幸福值和最长的路线.
他们不愿再经历之前的大起大落,所以决定连续几天的幸福值波动不能超过M.他们想知道要是这样的话他们最多能连续锻炼多少天(hint:不一定从第一天一直开始连续锻炼)?
现在，他们把这个艰巨的任务交给你了!
Input
第一行包含两个整数N, M(M<=10^9).
第二至第N行,每行两个数字Fi , Di, 第i行表示第i个节点的父亲是Fi,且道路的幸福值是Di.
Output
最长的连续锻炼天数
Solution
首先我们要把点权求出来。
那么我们设1为根节点，用两个数组fir[i]和sec[i]维护从节点i开始最长的路径和次长的路径。
第一次先求出起点为i终点在i的子树内的最长路和次长路，第二次再求出每个节点往其父节点走的最长路径。
接着就要求最大的区间，这里我一开始的想法是用数据结构来维护，set或者线段树什么的应该都行，但是我们注意到n<=1000000，则这么干有可能会超时。
那么我们就改用单调栈来维护最大值和最小值。
第一个单调栈保证里面的元素严格递增，第二个单调栈保证里面的元素严格递减，那么最大值就是第二个单调栈的栈底，最小值就是第一个单调栈的栈顶，我们只需要每次插入i时同时维护这两个单调栈即可。
Code
type
arr=record
y,w,next:longint;
end;
arrr=record
num,len:longint;
end;
var
nm,n,m,ans:longint;
a:array [0..2000001] of arr;
fir,sec,st1,st2:array [0..1000001] of arrr;
l,r:array [1..2] of longint;
ls:array [0..1000001] of longint;
function max(o,p:longint):longint;
begin
if o>p then exit(o);
exit(p);
end;
procedure add(u,v,z:longint);
begin
inc(nm);
with a[nm] do
begin
y:=v; w:=z;
next:=ls[u];
ls[u]:=nm;
end;
end;
procedure dfs1(x,fa:longint);
var
i:longint;
begin
i:=ls[x];
while i<>0 do
with a[i] do
begin
if y=fa then
begin
i:=next;
continue;
end;
dfs1(y,x);
if fir[y].len+w>fir[x].len then
begin
sec[x]:=fir[x];
fir[x].len:=fir[y].len+w;
fir[x].num:=y;
end else
if fir[y].len+w>sec[x].len then
begin
sec[x].len:=fir[y].len+w;
sec[x].num:=y;
end;
i:=next;
end;
end;
procedure dfs2(x,fa,len:longint);
var
i,t:longint;
begin
if fir[fa].num=x then t:=sec[fa].len+len
else t:=fir[fa].len+len;
if t>fir[x].len then
begin
sec[x]:=fir[x];
fir[x].len:=t;
fir[x].num:=fa;
end else
if t>sec[x].len then
begin
sec[x].len:=t;
sec[x].num:=fa;
end;
i:=ls[x];
while i<>0 do
with a[i] do
begin
if y=fa then
begin
i:=next;
continue;
end;
dfs2(y,x,w);
i:=next;
end;
end;
procedure init;
var
i,x,y:longint;
begin
fillchar(ls,sizeof(ls),0);
readln(n,m); nm:=0;
for i:=2 to n do
begin
readln(x,y);
add(x,i,y);
add(i,x,y);
end;
end;
procedure main;
var
i,ll,t:longint;
begin
l[1]:=1; l[2]:=1; r[1]:=0; r[2]:=0;
ans:=0; ll:=1;
for i:=1 to n do
begin
t:=fir[i].len;
while (l[1]<=r[1]) and (st1[r[1]].len>=t) do
dec(r[1]);
inc(r[1]);
st1[r[1]].len:=t;
st1[r[1]].num:=i;
while (l[2]<=r[2]) and (st2[r[2]].len<=t) do
dec(r[2]);
inc(r[2]);
st2[r[2]].len:=t;
st2[r[2]].num:=i;
while st2[l[2]].len-st1[l[1]].len>m do
if st1[l[1]].num<st2[l[2]].num then
begin
ll:=st1[l[1]].num+1;
inc(l[1]);
end else
begin
ll:=st2[l[2]].num+1;
inc(l[2]);
end;
ans:=max(ans,i-ll+1);
end;
end;
begin
init;
dfs1(1,0);
dfs2(1,0,0);
main;
write(ans);
end.