BZOJ 2500: 幸福的道路 树形DP+双指针

换根DP 求一下每个点为起点的最长路径，然后用双指针扫一下统计答案就好了. 

code:

#include <cstdio> 
#include <queue>
#include <set>
#include <algorithm>     
#define N 1000007        
#define ll long long                     
#define setIO(s) freopen(s".in","r",stdin)   
using namespace std; 
multiset<int>S;  
multiset<int>::iterator it;  
int pre() { return *S.begin(); }  
int end() { it=S.end();--it; return *it; }
int n,m,edges;    
int f1[N],f2[N],g[N];  
int hd[N],to[N],nex[N],val[N];    
void add(int u,int v,int c) 
{
    nex[++edges]=hd[u],hd[u]=edges,to[edges]=v,val[edges]=c;  
} 
void dfs(int x) 
{
    f1[x]=f2[x]=0; 
    for(int i=hd[x];i;i=nex[i]) 
    {
        int y=to[i]; 
        dfs(y);   
        if(f1[y]+val[i]>f1[x]) f2[x]=f1[x],f1[x]=f1[y]+val[i];  
        else  f2[x]=max(f2[x],f1[y]+val[i]);                          
    }           
}    
void dfs2(int x)
{ 
    if(x==1) g[x]=f1[x]; 
    for(int i=hd[x];i;i=nex[i]) 
    {
        int y=to[i],tmp=0;     
        if(f1[y]+val[i]==f1[x]) g[y]=max(f1[y],val[i]+f2[x]),tmp=f2[x]+val[i];  
        else g[y]=max(f1[y],val[i]+f1[x]),tmp=f1[x]+val[i];   
        if(tmp>f1[y]) f2[y]=f1[y],f1[y]=tmp;   
        else f2[y]=max(f2[y],tmp); 
        dfs2(y);
    }
}
int main() 
{   
    setIO("input");  
    int i,j;       
    scanf("%d%d",&n,&m);   
    for(i=2;i<=n;++i) 
    {
        int ff,v; 
        scanf("%d%d",&ff,&v),add(ff,i,v);  
    }
    dfs(1);    
    dfs2(1);      
    int l=1,r=1,ans=1;      
    for(r=1;r<=n;++r) 
    {    
        S.insert(g[r]);     
        while(S.size()>1&&end()-pre()>m) S.erase(S.lower_bound(g[l])),++l;      
        ans=max(ans,r-l+1);      
    }      
    printf("%d
",ans); 
    return 0;   
}