참고 자료
제목:
n개의 점에 대한 테두리 트리 Q개의 질문을 지정합니다.
아래 n-1행은 나무를
dp[i]를 설정하면 나무에서 i점에서 가장 먼 거리를 나타낸다
다음 Q행의 각 행의 숫자는 문의를 나타냅니다.
L 을 묻는 것은 dp 수조에서 가장 긴 연속 서열을 구해서 서열의 최대 값인 최소 값인 <=L을 출력하고 이 서열의 길이를 출력하는 것을 의미합니다.
아이디어:
dp수조를 구하는 것은 나무의 직경을 구하고 dfs를 구하는 것이다.
이어서 이 문제와 같다.
모든 문의에 대해 단조로운 대기열로 유지할 수 있습니다.O(n)의 대답.

Bob’s Race

Time Limit: 5000/2000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 2639    Accepted Submission(s): 840
Problem Description
Bob wants to hold a race to encourage people to do sports. He has got trouble in choosing the route. There are N houses and N - 1 roads in his village. Each road connects two houses, and all houses are connected together. To make the race more interesting, he requires that every participant must start from a different house and run AS FAR AS POSSIBLE without passing a road more than once. The distance difference between the one who runs the longest distance and the one who runs the shortest distance is called “race difference” by Bob. Bob does not want the “race difference”to be more than Q. The houses are numbered from 1 to N. Bob wants that the No. of all starting house must be consecutive. He is now asking you for help. He wants to know the maximum number of starting houses he can choose, by other words, the maximum number of people who can take part in his race.
 
Input
There are several test cases.
The first line of each test case contains two integers N and M. N is the number of houses, M is the number of queries.
The following N-1 lines, each contains three integers, x, y and z, indicating that there is a road of length z connecting house x and house y.
The following M lines are the queries. Each line contains an integer Q, asking that at most how many people can take part in Bob’s race according to the above mentioned rules and under the condition that the“race difference”is no more than Q. 
The input ends with N = 0 and M = 0.
(N<=50000 M<=500 1<=x,y<=N 0<=z<=5000 Q<=10000000)
 
Output
For each test case, you should output the answer in a line for each query.
 
Sample Input

   
   
   
   

    
    
    
    5 5
1 2 3
2 3 4
4 5 3
3 4 2
1
2
3
4
5
0 0
   
   
   
   

 
Sample Output

   
   
   
   

    
    
    
    1
3
3
3
5
   
   
   
   

 
Source
2011 Asia Fuzhou Regional Contest

#include<iostream>
#include<cstring>
#include<cstdio>
#include<queue>
#include <cmath>
using namespace std;
#define ll long long
#define prt(k) ;//cerr<<#k" = "<<k<<endl
const int N = 50050;
const int M = 2 * N;
int n, m;
const ll inf = 0x3f3f3f3f;
int head[M], to[M], next[M], cost[M];
int tot;
void initEdge()
{
    tot = 0;
    memset(head, -1, sizeof head);
}
void addEdge(int u, int v, int w)
{
    to[++tot] = v, cost[tot] = w;
    next[tot] = head[u];
    head[u] = tot;
}
ll dis[N];
int pre[N];
int BFS(int x)  ///return farest point from x
{
    memset(dis, -1, sizeof dis);
    dis[x] = 0;
    pre[x] = -1;
    int far = x;
    queue<int> q;
    q.push(x);
    while(!q.empty())
    {
        int u=q.front();q.pop();
        for(int i=head[u];~i;i=next[i])
        {
            int v = to[i];
            if(dis[v]==-1)
            {
                dis[v] = dis[u] + cost[i];
                pre[v] = u;
                if(dis[far] < dis[v])
                    far = v;
                q.push(v);
            }
        }
    }
    return far;
}
ll dp[N];
bool vis[N];
void dfs(int u)
{
    vis[u] = true;
    for(int i=head[u];~i;i=next[i])
    {
        int v = to[i];
        if(vis[v]) continue;
        dp[v] = dp[u] + cost[i];
        dfs(v);
    }
}
int stk[N];
int len;
void build()    ///       
{
    int E = BFS(1);
    int S = BFS(E);
    int top = 0;
    int u = S;
    len = dis[S];
    memset(vis, 0, sizeof vis);
    while(u != -1)
    {
        stk[top++] = u;
        dp[u] = max(dis[u], len - dis[u]);
        vis[u] = true;
        u = pre[u];
    }
    for(int i=0;i<top;i++)  dfs(stk[i]);
}
int qMax[M], qMin[M];
int main()
{
  //  freopen("in.txt","r",stdin);
    while(scanf("%d%d",&n,&m)==2, n+m)
    {
        initEdge();
        for(int i=0;i<n-1;i++)
        {
            int u,v,w;
            scanf("%d%d%d", &u,&v,&w);
            addEdge(u,v,w);
            addEdge(v,u,w);
        }
        build();
       // for(int i=1;i<=n;i++) printf("dp[%d] = %d
",i,dp[i]);
        while(m--)
        {
            int v; scanf("%d",&v);
            int ans, hmax, tmax, hmin, tmin;
            ans=hmax=tmax=hmin=tmin=0;
            int st = 0;
            tmax=tmin=-1;
            for(int i=1;i<=n;i++)
            {
                while(hmax<=tmax&&dp[qMax[tmax]]<dp[i]) --tmax;
                qMax[++tmax] = i;
                while(hmin<=tmin&&dp[qMin[tmin]]>dp[i]) --tmin;
                qMin[++tmin] = i;
                while(dp[qMax[hmax]]-dp[qMin[hmin]] > v)
                {
                    if(qMax[hmax]<=qMin[hmin])
                        st = qMax[hmax++];
                    else
                        st = qMin[hmin++];
                }
                ans=max(ans, i-st);
            }
            printf("%d
", ans);
        }
    }
}