考试的时候打了个树链剖分，而且还审错题了，以为是每天找所有点的最长路，原来是每天起点的树上最长路径再搞事情。。
先用dfs处理出来每个节点以他为根的子树的最长链和次长链。（后面会用到）
然后用类似dp的方法把每个节点的最长路径求出来。
下面是具体解释，请思考
以一个节点为例（w为它与父亲节点道路的权值）
一、如果它父亲节点的最长路径不过它
那么它最长路径等于它父亲最长路径+w（自己画图即可理解，往上走的）
它的次长路径等于它的最长链（只能往下走）
二、如果过它
那么它的最长路径有两种可能
①它的最长链
②它父亲的次长路径+w
如果①优，那么它最长路径为①，次长路径为max（它的次长链，②）
如果②优，那么它最长路径为②，次长路径为①
很好理解吧。。。
然后让求最大值与最小值差在m之内的最长子串。
据他们说有O（n）的做法，不过我打了O（nlogn）的打法，跑进了1s，反正O（能过）就行。
我的nlogn是二分答案+单调队列。二分答案去验证，挨个移动，看是否满足条件。
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
#define pos(i,a,b) for(int i=(a);i<=(b);i++)
#define pos2(i,a,b) for(int i=(a);i>=(b);i--)
int n,m;
#define N 1001000
struct haha
{
int to,next,w;
};
int read()
{
int x=0;
char ch=getchar();
while(ch<'0'||ch>'9')
ch=getchar();
while(ch>='0'&&ch<='9')
x=x*10+ch-'0',ch=getchar();
return x;
}
haha edge[N*4];
int head[N],cnt=1;
void add(int u,int v,int w)
{
edge[cnt].w=w;
edge[cnt].to=v;
edge[cnt].next=head[u];
head[u]=cnt++;
}
struct qian
{
int fir,firch; int sec,secch;
int roadfir,roadsec;int roadfirch,roadsecch;
}cun[N];
int fa[N];
void dfs(int now)
{
for(int i=head[now];i;i=edge[i].next)
{
int to=edge[i].to;
int w=edge[i].w;
dfs(to);
if(cun[now].sec<cun[to].fir+w)
{
cun[now].sec=cun[to].fir+w;
cun[now].secch=to;
if(cun[now].sec>cun[now].fir)
{
swap(cun[now].sec,cun[now].fir);
swap(cun[now].secch,cun[now].firch);
}
}
}
}
void dp(int now,int w)
{
if(now==1)
{
cun[now].roadfir=cun[now].fir;
cun[now].roadsec=cun[now].sec;
cun[now].roadfirch=cun[now].firch;
cun[now].roadsecch=cun[now].secch;
}
else
{
if(cun[fa[now]].roadfirch!=now)
{
cun[now].roadfir=cun[fa[now]].roadfir+w;
cun[now].roadfirch=fa[now];
cun[now].roadsec=cun[now].fir;
}
else
{
if(cun[now].fir>cun[fa[now]].roadsec+w)
{
cun[now].roadfir=cun[now].fir;
cun[now].roadfirch=cun[now].firch;
cun[now].roadsec=max(cun[now].sec,cun[fa[now]].roadsec+w);
}
else
{
cun[now].roadfir=cun[fa[now]].roadsec+w;
cun[now].roadfirch=fa[now];
cun[now].roadsec=cun[now].fir;
}
}
}
for(int i=head[now];i;i=edge[i].next)
{
int to=edge[i].to;
int ww=edge[i].w;
dp(to,ww);
}
}
int f[N];
int qmax[N],hed,tail;
int qmin[N],beg,ed;
bool find(int val){
hed=tail=0;
beg=ed=0;
for(int i=1;i<=n;i++){
while(hed<tail&&i-qmax[hed]>=val) hed++;
while(beg<ed&&i-qmin[beg]>=val) beg++;
while(hed<tail&&f[qmax[tail-1]]<f[i]) tail--;qmax[tail++]=i;
while(beg<ed&&f[qmin[ed-1]]>f[i]) ed--;qmin[ed++]=i;
if(i>=val&&f[qmax[hed]]-f[qmin[beg]]<=m) return true;
}
return false;
}
int main()
{
//freopen("race.in","r",stdin);
//freopen("race.out","w",stdout);
n=read();m=read();
pos(i,2,n)
{
int x,y;
x=read();y=read();
add(x,i,y);
fa[i]=x;
}
dfs(1);
dp(1,0);
for(int i=1;i<=n;i++)
cout<<cun[i].roadfir<<" "<<cun[i].roadsec<<endl;
while(1);
for(int i=1;i<=n;i++)
f[i]=cun[i].roadfir;
int l=1,r=n+1;
while(l<r-1){
int mid=l+r>>1;
if(find(mid))l=mid;
else r=mid;
}
int l=1,r=n+1;
while(l<r-1)
{
int mid=(l+r)>>1;
if(find(mid))
l=mid;
else
r=mid;
}
cout<<l;
//while(1);
return 0;
}