题解: 题目分为两问 求从每个点出发的最长链
求一段连续最长的区间让极差小于m
对于第一问 显然是树dp 我们考虑对于一个点的最长路径要么从父亲出发 要么是从儿子出发 这就是我们所谓的 "上搞搞下搞搞" 很显然的我们只需要维护从父亲走的最长路和从儿子走的最长路取max即可 我们设从儿子走的最长路径为maxx 从父亲走的最长路径为fmaxx 但是存在一种情况 设 y是x的父亲节点 它存在 maxx[y]=maxx[x]+x到y的边权 但这样的话你去更新fmaxx[x]时 就不能用最长儿子路径去更新 因为子树路径会走重复 所以我们用次大子树路径去更新最大儿子路径的fmaxx 总之我们需要维护三个 变量 从父亲走的最长路径 fmaxx 从儿子走的最长路径 maxx 从儿子走的次长路径 cmaxx
对于第二问 单调队列是可以直接做的(但是基本没写过单调队列) 我写的是倍增ST表 双指针扫过去
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <vector>
#include <stack>
#include <queue>
#include <cmath>
#include <set>
#include <map>
#define mp make_pair
#define pb push_back
#define pii pair<int,int>
#define link(x) for(edge *j=h[x];j;j=j->next)
#define inc(i,l,r) for(int i=l;i<=r;i++)
#define dec(i,r,l) for(int i=r;i>=l;i--)
#define ll long long
const int MAXN=1e6+10;
const double eps=1e-8;
using namespace std;
struct edge{int t,v;edge*next;}e[MAXN],*h[MAXN],*o=e;
void add(int x,int y,int vul){o->t=y;o->v=vul;o->next=h[x];h[x]=o++;}
ll read(){
ll x=0,f=1;char ch=getchar();
while(!isdigit(ch)){if(ch==‘-‘)f=-1;ch=getchar();}
while(isdigit(ch))x=x*10+ch-‘0‘,ch=getchar();
return x*f;
}
int maxx[MAXN],cmaxx[MAXN],a[MAXN];
void dfs1(int x,int fa){
link(x){
dfs1(j->t,x);
if(maxx[x]<maxx[j->t]+j->v)cmaxx[x]=maxx[x],maxx[x]=maxx[j->t]+j->v;
else if(cmaxx[x]<maxx[j->t]+j->v)cmaxx[x]=maxx[j->t]+j->v;
}
}
int fmaxx[MAXN];
void dfs2(int x,int fa){
a[x]=max(maxx[x],fmaxx[x]);
link(x){
int temp=(maxx[x]==maxx[j->t]+j->v?cmaxx[x]:maxx[x]);
temp=max(temp,fmaxx[x]);
fmaxx[j->t]=temp+j->v;
dfs2(j->t,x);
}
}
int dp1[MAXN][21],dp2[MAXN][21];
int ma[MAXN];
int get_max(int l,int r){
int k=r-l+1;
k=ma[k];
return max(dp1[l][k],dp1[r-(1<<k)+1][k]);
}
int get_min(int l,int r){
int k=r-l+1;
k=ma[k];
return min(dp2[l][k],dp2[r-(1<<k)+1][k]);
}
int n;int m;
bool check(int l,int r){
if(get_max(l,r)-get_min(l,r)<=m)return 1;
return 0;
}
int main(){
ma[1]=ma[0]=0;
inc(i,2,MAXN-1)ma[i]=ma[i/2]+1;
n=read();m=read();
int u;int k;
inc(i,2,n)u=read(),k=read(),add(u,i,k);
dfs1(1,0);dfs2(1,0);
inc(i,1,n)dp1[i][0]=dp2[i][0]=a[i];
inc(j,1,20){
for(int i=1;i+(1<<j)<=n+1;i++){
dp1[i][j]=max(dp1[i][j-1],dp1[i+(1<<(j-1))][j-1]);
dp2[i][j]=min(dp2[i][j-1],dp2[i+(1<<(j-1))][j-1]);
}
}
int tot=1;int ans=0;
inc(i,1,n){
while(tot<=n&&check(i,tot))tot++;
ans=max(ans,tot-i);
}
printf("%d\n",ans);
}
原文：https://www.cnblogs.com/wang9897/p/10343530.html