[文章目录]
Description
小T与小L终于决定走在一起,他们不想浪费在一起的每一分每一秒,所以他们决定每天早上一同晨练来享受在一起的时光.他们画出了晨练路线的草图,眼尖的小T发现可以用树来描绘这个草图.他们不愿枯燥的每天从同一个地方开始他们的锻炼,所以他们准备给起点标号后顺序地从每个起点开始(第一天从起点一开始,第二天从起点二开始……). 而且他们给每条道路定上一个幸福的值.很显然他们每次出发都想走幸福值和最长的路线(即从起点到树上的某一点路径中最长的一条).他们不愿再经历之前的大起大落,所以决定连续几天的幸福值波动不能超过M(即一段连续的区间并且区间的最大值最小值之差不超过M).他们想知道要是这样的话他们最多能连续锻炼多少天(hint:不一定从第一天一直开始连续锻炼)? 现在，他们把这个艰巨的任务交给你了!N<=1000 000
树形DP+双指针+单调队列。DP出每个点为端点的最长链（一开始当成了过该点的最长链，被自己蠢哭。。。）然后双指针+单调队列弄一下就好了。时间O(n).
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define N 1001000
int n,m;
int w[N];
int head[N],nxt[N],to[N],ran[N],mx[N],mx2[N],mf[N],ans[N],mxq[N],miq[N],tot,cnt;
inline void add(int x,int y) {to[++cnt]=y; nxt[cnt]=head[x]; head[x]=cnt;}
void dfs(int x)
{
ran[++tot]=x;
for(int i=head[x];i;i=nxt[i])
{
dfs(to[i]);
if(mx[to[i]]+w[to[i]]>mx[x]) mx2[x]=mx[x],mx[x]=mx[to[i]]+w[to[i]];
else if(mx[to[i]]+w[to[i]]>mx2[x]) mx2[x]=mx[to[i]]+w[to[i]];
}
}
int main()
{
scanf("%d%d",&n,&m); int x;
for(int i=2;i<=n;++i)
{
scanf("%d%d",&x,&w[i]);
add(x,i);
}
dfs(1);
for(int i=1;i<=n;++i)
{
x=ran[i]; mf[x]+=w[x];
for(int j=head[x];j;j=nxt[j])
{
if(mx[to[j]]+w[to[j]]==mx[x]) mf[to[j]]=max(mf[x],mx2[x]);
else mf[to[j]]=max(mf[x],mx[x]);
}
ans[x]=max(mf[x],mx[x]);
}
rint l=1,r=0,fna=0,h1=1,t1=0,h2=1,t2=0;
while(l<=n)
{
if(ans[mxq[h1]]-ans[miq[h2]]<=m)
{
fna=max(fna,r-l+1);
if(r<n)
{
r++;
while(h1<=t1&&ans[mxq[t1]]<ans[r]) t1--; mxq[++t1]=r;
while(h2<=t2&&ans[miq[t2]]>ans[r]) t2--; miq[++t2]=r;
}
else break;
}
else
{
if(mxq[h1]==l) ++h1;
if(miq[h2]==l) ++h2;
++l;
}
}
printf("%d",fna);
return 0;
}