幸福的道路(race)_综合

问题 C: 幸福的道路(race)

时间限制: 2 Sec 内存限制: 128 MB
提交: 83 解决: 33
[提交][状态][讨论版]

题目描述

小 T 与小 L 终于决定走在一起,他们不想浪费在一起的每一分每一秒,所以他们决定每天早上一同晨练来享受在一起的时光.
他们画出了晨练路线的草图,眼尖的小 T 发现可以用树来描绘这个草图. 他们不愿枯燥的每天从同一个地方开始他们的锻炼,所以他们准备给起点标号后顺序地从每个起点开始(第一天从起点一开始,第二天从起点二开始……). 而且他们给每条道路定上一个幸福的值.很显然他们每次出发都想走幸福值和最长的路线(即从起点到树上的某一点路径中最长的一条). 他们不愿再经历之前的大起大落,所以决定连续几天的幸福值波动不能超过 M(即一段连续的区间并且区间的最大值最小值之差不超过 M).他们想知道要是这样的话他们最多能连续锻炼多少天(hint:不一定从第一天一直开始连续锻炼)?
现在，他们把这个艰巨的任务交给你了!

输入

第一行包含两个整数 N, M(M<=10^9).
第二至第 N 行,每行两个数字 Fi , Di, 第 i 行表示第 i 个节点的父亲是 Fi,
且道路的幸福值是 Di.

输出

最长的连续锻炼天数

样例输入

3 2
1 1
1 3

样例输出

提示

50%的数据 N<=1000
 
 80%的数据 N<=100000
 
 100%的数据 N<=1000000
幸福的道路(race)
         这道题说来想哭，打了半天暴力freopen打错了。不然还能水10分。
         这道题比较有意思，我成功的想到了后半段正解：二分答案加单调队列。却万万没想到，前半部分我最迷惑的拿dfs就可以撸过。由题意可知，它强制要求走最长路，那么对于一个在树上的点来说它只能是向上走和向下走，向下走很简单，最长链，向上走就需要dfs第二遍了，因为这个节点向上走一定过父节点。若它在父节点的最长链上，就比较从次长链和父节点的走法那个大，若果不在最长链上，就比较最长链和父节点走法。最终得出每个点怎么走最大。
         由题目可知，他们不一定从第一天开始锻炼，因此挨个枚举起点，根据此性质可知用单调队列，其次，这个长度和显然满足二分的性质，因此为二分答案+单调队列。
         改题的时候将路的权值下传到了点，结果向下找的时候忘了这茬了，竟然对了70%，奇迹啊。

   #include<iostream>
  
   #include<cmath>
  
   #include<cstring>
  
   #include<cstdio>
  
   #include<cstdlib>
  
   #include<algorithm>
  
   #define LL long long
  
   #define V 1000005
  
   using
   namespace 
    std;
  
   int
   n,m;
  
   struct
   data
  
   {
    
   int
   to,next;   
  
   LL dis;
  
   }Edge[V];
  
   int
   ll,rr;
  
   int
   head[V],tot,son[V],s1[V];
  
   LL mi[V],mz[V],mx[V];
  
   inline
   void 
    add1(
   int
   x,
   int
   y,LL z)
  
   {
    
   Edge[tot].dis=z;
  
   Edge[tot].to=y;
  
   Edge[tot].next=head[x];
  
   head[x]=tot++;      
  
   }
  
   inline
   void 
    dfs(
   int
   x)
  
   {
    
   int
   v;
  
   for
   (
   int
   i=head[x];i!=-1;i=Edge[i].next) 
  
   {
    
   v=Edge[i].to;
  
   //if(head[v]!=-1)
  
   dfs(v);
  
   if
   (mx[v]+Edge[i].dis>=mx[x])
  
   {
    
   mi[x]=mx[x];
  
   mx[x]=mx[v]+Edge[i].dis;
  
   s1[x]=son[x];
  
   son[x]=v;
  
   }
  
   else
   if
   (mx[v]+Edge[i].dis>=mi[x])
  
   {
    
   s1[x]=v;
  
   mi[x]=mx[v]+Edge[i].dis;
  
   }
  
   }
  
   }
  
   inline
   void 
    dfs1(
   int
   x,LL num)
  
   {
    
   int
   v;
  
   mz[x]=max(mx[x],num);
  
   for
   (
   int
   i=head[x];i!=-1;i=Edge[i].next) 
  
   {
    
   v=Edge[i].to;
  
   if
   (v==son[x])
  
   dfs1(v,max(mi[x],num)+Edge[i].dis);
  
   else
  
   dfs1(v,max(mx[x],num)+Edge[i].dis);
  
   }
  
   }
  
   int
   head1,tail1,head2,tail2;
  
   int
   mp1[V],mp2[V];
  
   inline
   int 
    check(
   int
   len)
  
   {
    
   head1=tail1=head2=tail2=0;
  
   for
   (
   int
   i=1;i<=n;i++)
  
   {
    
   if
   (i>=len)
  
   {
    
   while
   (head1!=tail1&&mp1[head1]<i-len+1)
  
   head1++;
  
   while
   (head2!=tail2&&mp2[head2]<i-len+1)
  
   head2++;
  
   while
   (head2!=tail2&&mz[i]>=mz[mp2[tail2-1]])
  
   tail2--;
  
   mp2[tail2++]=i;
  
   while
   (head1!=tail1&&mz[i]<=mz[mp1[tail1-1]])
  
   tail1--;
  
   mp1[tail1++]=i;
  
   if
   (
   abs
   (mz[mp2[head2]]-mz[mp1[head1]])<=m)
  
   return
   1;
  
   continue
   ;
  
   }
  
   while
   (head2!=tail2&&mz[i]>=mz[mp2[tail2-1]])
  
   tail2--;
  
   mp2[tail2++]=i;
  
   while
   (head1!=tail1&&mz[i]<=mz[mp1[tail1-1]])
  
   tail1--;
  
   mp1[tail1++]=i;
  
   }
  
   return
   0; 
  
   }
  
   int
   main()
  
   {
    
   //freopen("in.txt","r",stdin); freopen("out.txt","w",stdout);
  
   //freopen("wbtree.in","r",stdin);freopen("wbtree.out","w",stdout);
  
   memset
   (head,-1,
   sizeof
   (head));
  
   cin>>n>>m;
  
   int
   a;
  
   LL b;
  
   for
   (
   int
   i=2;i<=n;i++)
  
   {
    
   scanf
   (
   "%d%lld"
   ,&a,&b);
  
   add1(a,i,b);
  
   }
  
   dfs(1);
  
   dfs1(1,0);
  
   int
   ans=0;
  
   //for(int i=1;i<=n;i++)
  
   //cout<<i<<"  "<<mx[i]<<endl;
  
   int
   l=1,r=n,mid;
  
   while
   (l<=r)
  
   {
    
   mid=(l+r)/2;
  
   if
   (check(mid)) l=mid+1;
  
   else
   r=mid-1;
  
   }
  
   cout<<r<<endl;  
  
   return
   0;
  
   }