树形DP+单调队列优化DP
好题（也是神题……玛雅我实在是太弱了TAT，真是一个250）
完全是抄的zyf的……orz我还是退OI保平安吧
第一步对于每一天求出一个从第 i 个点出发走出去的最长链的长度，树形DP解决……
g[x][0]表示从x的子树中，x到叶子的最长链，g[x][1]表示次长链。（用儿子更新父亲）
f[x]表示从x向上走到某个父亲，再向下的最长链。（用父亲更新儿子）
这个DP是通过两次从根出发的dfs实现的。
那么我们现在就得到了a[i]=max(f[i],g[i][0])表示从 i 出发的最长链的长度。
第二步是要在a数组中求一段最长的区间满足极差小于等于m。
这个居然可以单调队列QAQ（当然啦……右端点为1~n时，左端点也是单调向右移动的！）
用两个队列分别维护最大值和最小值，将当前结点入队后，如果最大值-最小值（两个队列的队头）>m，则选一个较小的队头，以 i 为右节点的最长区间 的左端点，就是较小的队头表示的位置+1，（扔掉那个最小的以后剩下的就合法了啊）（才怪！如果不合法，继续扔，边扔边更新答案）
sigh……DP真是一种神奇的算法……我还是too young too naive
UPD：2015-04-24 11:14:03
其实第二步我以前做过的QAQ，早忘了而已……
/**************************************************************
Problem: 2500
User: Tunix
Language: C++
Result: Accepted
Time:2496 ms
Memory:55960 kb
****************************************************************/ //Huce #1 C
#include<vector>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#define rep(i,n) for(int i=0;i<n;++i)
#define F(i,j,n) for(int i=j;i<=n;++i)
#define D(i,j,n) for(int i=j;i>=n;--i)
#define pb push_back
using namespace std;
inline int getint(){
int v=,sign=; char ch=getchar();
while(ch<''||ch>''){ if (ch=='-') sign=-; ch=getchar();}
while(ch>=''&&ch<=''){ v=v*+ch-''; ch=getchar();}
return v*sign;
}
const int N=1e6+,INF=~0u>>;
typedef long long LL;
/******************tamplate*********************/
int to[N],next[N],head[N],len[N],cnt;
void add(int x,int y,int z){
to[++cnt]=y; next[cnt]=head[x]; head[x]=cnt; len[cnt]=z;
}
int n,m;
LL f[N],g[N][],a[N];
void down(int x){
for(int i=head[x];i;i=next[i]){
down(to[i]);
if (g[to[i]][]+len[i]>g[x][]){
g[x][]=g[x][];
g[x][]=g[to[i]][]+len[i];
}else g[x][]=max(g[x][],g[to[i]][]+len[i]);
}
}
void up(int x){
int y;
for(int i=head[x];i;i=next[i]){
f[y=to[i]]=f[x]+len[i];
if (g[y][]+len[i]==g[x][]) f[y]=max(f[y],g[x][]+len[i]);
else f[y]=max(f[y],g[x][]+len[i]);
up(y);
}
}
int Q1[N],Q2[N];
int main(){
#ifndef ONLINE_JUDGE
freopen("C.in","r",stdin);
freopen("C.out","w",stdout);
#endif
n=getint(); m=getint();
int x,y,z;
F(i,,n){
x=getint(); z=getint();
add(x,i,z);
}
down(); up();
F(i,,n) a[i]=max(f[i],g[i][]);
LL ret=,ans=;int l1=,r1=-,l2=,r2=-;
F(i,,n){
while(l1<=r1 && a[i]<=a[Q1[r1]]) r1--;
Q1[++r1]=i;
while(l2<=r2 && a[i]>=a[Q2[r2]]) r2--;
Q2[++r2]=i;
while(a[Q2[l2]]-a[Q1[l1]]>m)
ret=Q1[l1]<Q2[l2] ? Q1[l1++]+ : Q2[l2++]+;
ans=max(ans,i-ret+);
}
printf("%lld\n",ans);
return ;
}
2500: 幸福的道路
Time Limit: 20 Sec Memory Limit: 256 MB
Submit: 153 Solved: 60
[Submit][Status][Discuss]
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
1 1
1 3
Sample Output
3
数据范围：
50%的数据N<=1000
80%的数据N<=100 000
100%的数据N<=1000 000
数据范围：
50%的数据N<=1000
80%的数据N<=100 000
100%的数据N<=1000 000