求最长的任意两元素差不超过M的子段——双指针+单调队列hdu4123

换根dp的部分比较容易，难点在于求求最长的任意两元素差不超过M的子段

首先会想到双指针维护（尺取法），如果p1,p2间的max-min>M,那么p1向右移动，直到p1,p2间的max-min>M

这个过程可以用线段树（ST）来询问max,min

另外有一种更强大的方案，因为只要max,min,所以只要维护两个单调队列来解决即可，当max-min>M时取队首元素最远的出队即可

/*
第一部分：求出数组a[]
第二部分：每次询问给出一个Q，求出最长的一段[L,R]使段中任意两个数据的差不超过Q
    用双指针进行维护，用两个单调队列维护这指针间的最大最小值，然后O(n)求每个询问 

*/
#include<bits/stdc++.h>
#include<queue>
using namespace std;
#define N 50006 
struct Edge{int to,nxt,w;}e[N<<1];
int head[N],tot,n,m;
void init(){memset(head,-1,sizeof head);tot=0;}
void add(int u,int v,int w){
    e[tot].to=v;e[tot].w=w;e[tot].nxt=head[u];head[u]=tot++;
}
int d[N],a[N];
void dfs1(int u,int pre){
    d[u]=0;
    for(int i=head[u];i!=-1;i=e[i].nxt){
        int v=e[i].to;
        if(v==pre)continue;
        dfs1(v,u);
        d[u]=max(d[u],d[v]+e[i].w);
    }
}
void dfs2(int u,int pre,int up){
    int mx1=0,mx2=0,id1=0,id2=0;
    for(int i=head[u];i!=-1;i=e[i].nxt){
        int v=e[i].to;
        if(v==pre)continue;
        if(d[v]+e[i].w>=mx1){
            mx2=mx1,id2=id1;
            mx1=d[v]+e[i].w,id1=v;
        }
        else if(d[v]+e[i].w>=mx2)
            mx2=d[v]+e[i].w,id2=v;
    }
    if(up>=mx1){
        mx2=mx1,id2=id1;
        mx1=up,id1=0;
    }
    else if(up>=mx2)
        mx2=up,id2=0;
    a[u]=mx1;    
    
    for(int i=head[u];i!=-1;i=e[i].nxt){
        int v=e[i].to;
        if(v==pre)continue;
        if(v==id1)
            dfs2(v,u,mx2+e[i].w);
        else dfs2(v,u,mx1+e[i].w);
    }
}

//双指针p,i,两个单调队列维护区间最大值，最小值 
void solve(int Q){
    deque<int>q1,q2;
    int res=0,p=1;
    for(int i=1;i<=n;i++){
        while(q1.size() && a[q1.back()]>=a[i])q1.pop_back();
        q1.push_back(i); 
        while(q2.size() && a[q2.back()]<=a[i])q2.pop_back();
        q2.push_back(i); 
        
        while(a[q2.front()]-a[q1.front()]>Q){
            p=min(q1.front(),q2.front())+1;
            while(q1.front()<p)q1.pop_front();
            while(q2.front()<p)q2.pop_front();
        }
        res=max(res,i-p+1);
    }
    cout<<res<<endl;
} 

int main(){
    while(cin>>n>>m && n){
        init();
        for(int i=1;i<n;i++){
            int u,v,w;
            scanf("%d%d%d",&u,&v,&w);
            add(u,v,w);add(v,u,w);
        }
        dfs1(1,1);
        dfs2(1,1,0);
        while(m--){
            int q;scanf("%d",&q);
            solve(q);
        }
    }    
}