好题。。
先找出每个节点的树上最长路
由树形DP完成
节点x，设其最长路的子节点为y
对于y的最长路，有向上和向下两种情况：
down：y向子节点的最长路g[y][0]
up：x的次长路的g[x][1]+dis[x][y]
up：up[fa[x]]+dis[x][y]
dfs1找向下，即向子节点的最长路
dfs2找向上的最长路
最后最长路f[i]=max(up[x],g[x][0])
第二部分
找最长连续子序列，使得序列中abs(mx-mn)<=m
这次学习了用单调队列的做法
两个队列mx，mn
mx存单减的f[i]的i，mn单增
由于差值不大于m
每次找出front的最小值出队就行了
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<queue>
#define LL long long
using namespace std;
;
struct node{
int to,next;
LL cost;
}e[maxn];
int n,m,tot,x;
LL g[maxn][],f[maxn],y,head[maxn];
void insert(int u, int v, LL c){
e[++tot].to=v; e[tot].next=head[u]; head[u]=tot; e[tot].cost=c;
}
#define v e[i].to
void dfs1(int u){
; i=e[i].next){
dfs1(v);
]<g[v][]+e[i].cost){
g[u][]=max(g[u][],g[u][]);
g[u][]=g[v][]+e[i].cost;
}]=max(g[u][],g[v][]+e[i].cost);
}
}
void dfs2(int u){
; i=e[i].next){
f[v]=f[u]+e[i].cost;
]+e[i].cost==g[u][]) f[v]=max(f[v],g[u][]+e[i].cost);
]+e[i].cost);
dfs2(v);
}
}
int main(){
scanf("%d%d", &n, &m);
tot=; memset(head,-,sizeof(head));
; i<=n; i++){
int x; LL y;
scanf("%d%lld", &x, &y);
insert(x,i,y);
}
dfs1();
dfs2();
; i<=n; i++) f[i]=max(f[i],g[i][]);
deque<int> mx,mn;
;
;
; i<=n; i++){
while (!mx.empty() && f[mx.back()]<=f[i]) mx.pop_back();
while (!mn.empty() && f[mn.back()]>=f[i]) mn.pop_back();
mx.push_back(i); mn.push_back(i);
while (f[mx.front()]-f[mn.front()]>m){
if (mx.front()<mn.front()){
st=mx.front()+;
mx.pop_front();
}
else{
st=mn.front()+;
mn.pop_front();
}
}
ans=max(ans,i-st+);
}
printf("%d\n", ans);
;
}