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 <bits/stdc++.h>
#define ll long long
using namespace std;
struct nod{int t;ll v;nod(int t=0,ll v=0):t(t),v(v){}};
vector<nod>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<e[x].size();i++)if((t=e[x][i].t)!=F)dfs1(t,x),d[x]=max(d[x],d[t]+e[x][i].v);}
void dfs2(int x,int F)
{
ll fm=0,sm=0;
for(int i=0,t;i<e[x].size();i++) if((t=e[x][i].t)!=F)
{
if(d[t]+e[x][i].v>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<e[x].size();i++) if((t=e[x][i].t)!=F)
{
if(d[t]+e[x][i].v==fm) u[t]=max(u[t],sm+e[x][i].v);
else u[t]=max(u[t],fm+e[x][i].v);
dfs2(t,x);
}
}
int main()
{
scanf("%d%lld",&n,&m);
for(int i=2;i<=n;i++) scanf("%d%lld",&x,&y),e[i].push_back(nod(x,y)),e[x].push_back(nod(i,y));
dfs1(1,0);dfs2(1,0);
for(int i=1;i<=n;i++) a[i]=max(u[i],d[i]);
for(int i=1;i<=n;i++)
{
while(l1<=r1&&a[i]<=a[q1[r1]]) r1--;
while(l2<=r2&&a[i]>=a[q2[r2]]) r2--;
q1[++r1]=i;q2[++r2]=i;
while(a[q2[l2]]-a[q1[l1]]>m) if(q2[l2]<q1[l1]) g=q2[l2]+1,l2++;else g=q1[l1]+1,l1++;
ans=max(ans,i-g+1);
}
printf("%d\n",ans);
}