题目描述
小 T 与小 L 终于决定走在一起,他们不想浪费在一起的每一分每一秒,所以他们决定每天早上一同晨练来享受在一起的时光.
他们画出了晨练路线的草图,眼尖的小 T 发现可以用树来描绘这个草图.他们不愿枯燥的每天从同一个地方开始他们的锻炼,所以他们准备给起点标号后顺序地从每个起点开始(第一天从起点一开始,第二天从起点二开始……).而且他们给每条道路定上一个幸福的值.很显然他们每次出发都想走幸福值和最长的路线(即从起点到树上的某一点路径中最长的一条).他们不愿再经历之前的大起大落,所以决定连续几天的幸福值波动不能超过M(即一段连续的区间并且区间的最大值最小值之差不超过 M).他们想知道要是这样的话他们最多能连续锻炼多少天(hint:不一定从第一天一直开始连续锻炼)?
现在，他们把这个艰巨的任务交给你了!
他们画出了晨练路线的草图,眼尖的小 T 发现可以用树来描绘这个草图.他们不愿枯燥的每天从同一个地方开始他们的锻炼,所以他们准备给起点标号后顺序地从每个起点开始(第一天从起点一开始,第二天从起点二开始……).而且他们给每条道路定上一个幸福的值.很显然他们每次出发都想走幸福值和最长的路线(即从起点到树上的某一点路径中最长的一条).他们不愿再经历之前的大起大落,所以决定连续几天的幸福值波动不能超过M(即一段连续的区间并且区间的最大值最小值之差不超过 M).他们想知道要是这样的话他们最多能连续锻炼多少天(hint:不一定从第一天一直开始连续锻炼)?
现在，他们把这个艰巨的任务交给你了!
输入
第一行包含两个整数 N, M(M<=10^9).
第二至第 N 行,每行两个数字 Fi , Di, 第 i 行表示第 i 个节点的父亲是 Fi,
且道路的幸福值是 Di.
第二至第 N 行,每行两个数字 Fi , Di, 第 i 行表示第 i 个节点的父亲是 Fi,
且道路的幸福值是 Di.
输出
最长的连续锻炼天数
样例输入
3 2
1 1
1 3
样例输出
3
提示
50%的数据 N<=1000
80%的数据 N<=100000
100%的数据 N<=1000000
考试A掉了。。其实考试时候就用三个傻样例检查出来错误，再次心疼一发昨天被爆内存吓炸且不会数数的lc大佬，把1000000看成10^7。。
这题首先题目强制要求每天走幸福指数最高的链，那么dfs可以求出以u为根节点的子树的最长和次长链，如果每个节点都dfs一遍显然是可以求出来每个节点的ans的，但n^2的时间复杂度绝对是不能忍受的，所以我们再次进行dfs，那么对于u来说第一种情况是在子树中xjb搞，第二种是通过父亲再次走其他链，那么我们就需要一个参数，为从根节点到u最长链的长度，到每一个节点再用当前节点的最大或最小值来更新，额感觉说不太清，然后可以通过二分长度+维护两个单调队列来判断，如果存在一段区间使得最大-最小<=m 就为可行解。
code：
#define MAXN 1000005
#include <stdio.h>
#include <cstring>
#include <iostream>
#include <vector>
using namespace std;
int n,m,first[MAXN],e=1;
int w[MAXN][2],son[MAXN][2],ans[MAXN],f[MAXN][2];
typedef pair<int,int> pa;
struct edge{
int u,v,w,next;
}a[MAXN];
void push(int u,int v,int w){
a[e].u=u;
a[e].v=v;
a[e].w=w;
a[e].next=first[u];
first[u]=e++;
}
void dfs(int u){//第一个dfs，求次长和最长链，w[u][0]为最长链
for(int i=first[u];i;i=a[i].next){
dfs(a[i].v);
if(w[a[i].v][0]+a[i].w>w[u][0]){
w[u][1]=w[u][0];
w[u][0]=a[i].w+w[a[i].v][0];
son[u][1]=son[u][0];
son[u][0]=a[i].v;
}
else if(w[a[i].v][0]+a[i].w>w[u][1]){
son[u][1]=a[i].v;
w[u][1]=w[a[i].v][0]+a[i].w;
}
}
}
void dp(int u,int fa,int val,int len_x){//len_x为上述的第二种情况
if(u==1)ans[u]=w[u][0],f[u][0]=w[u][0],f[u][1]=w[u][1];//比较蠢的特判好像没用
else{
ans[u]=w[u][0];
if(u!=son[fa][0])ans[u]=w[fa][0]+val;//情况1：在子树中
if(ans[u]<len_x)ans[u]=len_x;//情况2：通过父亲走，用len_x更新
}
for(int i=first[u];i;i=a[i].next){
if(a[i].v!=son[u][0])
dp(a[i].v,u,a[i].w,max(len_x,w[u][0])+a[i].w);//如果不是最长连儿子，用最长链更新
else dp(a[i].v,u,a[i].w,max(len_x,w[u][1])+a[i].w);
}
}
int c[MAXN],b[MAXN],l,r;
int C[MAXN],B[MAXN],L,R;
bool ok(int len){
l=1,r=0;L=1,R=0;
for(int i=1;i<=len-1;i++){//先塞进去len-1个保证区间长度
while(l<=r&&c[r]>=ans[i])r--;
c[++r]=ans[i];
b[r]=i;
while(L<=R&&C[R]<=ans[i])R--;
C[++R]=ans[i];
B[R]=i;
}
for(int i=len;i<=n;i++){
while(l<=r&&c[r]>=ans[i])r--;
c[++r]=ans[i];
b[r]=i;
while(l<=r&&i-b[l]+1>len)l++;
while(L<=R&&C[R]<=ans[i])R--;
C[++R]=ans[i];
B[R]=i;
while(L<=R&&i-B[L]+1>len)L++;
if(C[L]-c[l]<=m)return 1;
}
return 0;
}
int main(){
//freopen("race.in","r",stdin);
//freopen("race.out","w",stdout);
scanf("%d%d",&n,&m);
for(int i=2;i<=n;i++){
int f,d;
scanf("%d%d",&f,&d);
push(f,i,d);
}
dfs(1);dp(1,0,0,0);
int l1=1,r1=n,Ans=0;
while(l1<=r1){//二分
int mid = l1+r1>>1;
if(ok(mid))Ans=mid,l1=mid+1;
else r1=mid-1;
}
printf("%d
",Ans);
}