题目描述

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

题目分析

第一问树形DP即可 拿出每个点的子树里的点 和根距离的次大值和最大值
第二问双指针+线段树 (单调队列更方便哦)

#include <cstdio>
#include <cstring>
#include <cmath>
#include <queue>
#include <algorithm>
using namespace std;
const int maxn=1000010;
int n,k,p,q;
int head[maxn],val[maxn<<1],to[maxn<<1],net[maxn<<1];
struct your
{
    long long big;
    long long biger;
    int big_num;
    int biger_num;
}dis[maxn];
long long fasum[maxn];
long long sum[maxn];
int tot;
void add(int x,int y,int c)
{
    net[++tot]=head[x];
    to[tot]=y;
    val[tot]=c; 
    head[x]=tot;
}
int fa[1000010];
void dfs1(int x)
{   
    for(int i=head[x];i;i=net[i])
    {
        if(to[i]==fa[x]) continue;
        dfs1(to[i]);
        if(dis[x].biger<dis[to[i]].biger+val[i])
        {
            dis[x].big=dis[x].biger;
            dis[x].big_num=dis[x].biger_num;
            dis[x].biger=dis[to[i]].biger+val[i];
            dis[x].biger_num=to[i];
            continue;
        }
        if(dis[x].big<dis[to[i]].biger+val[i])
        {
            dis[x].big=dis[to[i]].biger+val[i];
            dis[x].big_num=to[i];
        }
    }
}
long long check(int x,int temp,int c)
{
    long long tmp=fasum[temp];
    if(tmp<dis[temp].biger&&dis[temp].biger_num!=x)
        tmp=dis[temp].biger;
    if(tmp<dis[temp].big&&dis[temp].big_num!=x)
        tmp=dis[temp].big;
    return tmp+c;
}
void dfs2(int x,int c)
{
    fasum[x]=check(x,fa[x],c);
    for(int i=head[x];i;i=net[i])
    {
        if(to[i]==fa[x]) continue;
        dfs2(to[i],val[i]);
    }
    return ;
}
struct tree
{
    int x,y;
    long long maxx,minn,sum;
}a[maxn<<2];
void build(int dx,int dy,int num)
{
    a[num].x=dx,a[num].y=dy;
    if(dx==dy)
    {
        a[num].maxx=sum[dx];
        a[num].minn=sum[dx];
        return ;
    }
    a[num].minn=0x7f7f7f7f;
    int mid=(dx+dy)>>1;
    build(dx,mid,num<<1);
    build(mid+1,dy,num<<1|1);
    a[num].maxx=max(a[num<<1].maxx,a[num<<1|1].maxx);
    a[num].minn=min(a[num<<1].minn,a[num<<1|1].minn);
    return ;
}
long long getmin(int dx,int dy,int num)
{
    if(dx==a[num].x&&dy==a[num].y)
        return a[num].minn;
    int mid=(a[num].x+a[num].y)>>1;
    if(dx>mid) return getmin(dx,dy,num<<1|1);
    if(dy<=mid) return getmin(dx,dy,num<<1);
    return min(getmin(dx,mid,num<<1),getmin(mid+1,dy,num<<1|1));
}
long long getmax(int dx,int dy,int num)
{
    if(dx==a[num].x&&dy==a[num].y)
        return a[num].maxx;
    int mid=(a[num].x+a[num].y)>>1;
    if(dx>mid) return getmax(dx,dy,num<<1|1);
    if(dy<=mid) return getmax(dx,dy,num<<1);
    return max(getmax(dx,mid,num<<1),getmax(mid+1,dy,num<<1|1));
}
struct make
{
    long long sum,c;
};
void work()
{
    int l=1,r=0;
    int ans=0;
    for(int i=1;i<=n;i++)
    {
        r++;
        int tmp;
        tmp=getmax(l,r,1)-getmin(l,r,1);
        if(tmp<=k) ans=max(ans,r-l+1);
        else
        {
            while(l<r&&tmp>k)
            {
                l++;
                tmp=getmax(l,r,1)-getmin(l,r,1);
            }
            if(tmp<=k) ans=max(ans,r-l+1);
        }
    }
    printf("%d",ans);
}
int main()
{
    scanf("%d%d",&n,&k);
    for(int i=2;i<=n;i++)
    {
        int c;
        scanf("%d%d",&fa[i],&c);
        add(fa[i],i,c);
    }
    dfs1(1),dfs2(1,0);
    for(int i=1;i<=n;i++)
        sum[i]=max(fasum[i],dis[i].biger);
    build(1,n,1);
    work();
    return 0;
}