程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> hdu 4123 Bob’s Race （樹的直徑相關+rmq+單調隊列思想）

hdu 4123 Bob’s Race （樹的直徑相關+rmq+單調隊列思想）

編輯：C++入門知識

Bob’s Race

Time Limit: 5000/2000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 2115 Accepted Submission(s): 658

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

Sample Output

Source 2011 Asia Fuzhou Regional Contest
題意：先求遍樹上的每個點i，能走的最遠距離記錄為val[i]，然後有m個詢問，每次詢問一個q，求一個最大值減最小值不超過q的最長連續區間。

思路：先求樹的直徑兩個端點，然後求出每個點到這兩個點的距離，有一個結論為點到樹上的最遠點必為兩個端點之一（如果不是的話，那麼直徑就要換了，反證法），根據此性質求出val數組。對於每一個詢問，掃描一遍，假設j>i，那麼以j結尾的最長連續區間的起點必定不小於i的起點（顯然），根據這個單調性質，可以用單調隊列的思想處理起點，結尾的點枚舉即可，判斷一個區間內的點是否滿足max-min<=q就是用rmq來解決了。 ps：rmq最好預處理lg數組，單調隊列只是+n的復雜度。
代碼：

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#pragma comment (linker,"/STACK:102400000,102400000")
#define maxn 50005
#define MAXN 100005
#define mod 1000000009
#define INF 0x3f3f3f3f
#define pi acos(-1.0)
#define eps 1e-6
typedef long long ll;
using namespace std;

int n,m,ans,cnt,tot,flag;
int len,st,ed;   // 直徑 起點 終點
bool vis[maxn];
int head[maxn],val[maxn],dist[maxn][2];
int f[maxn][20],g[maxn][20],lg[maxn];  //第二維為二進制
struct Node
{
    int v,w,next;
} edge[MAXN];

void addedge(int u,int v,int w)
{
    cnt++;
    edge[cnt].v=v;
    edge[cnt].w=w;
    edge[cnt].next=head[u];
    head[u]=cnt;
}
void dfs(int u,int fa,int sum)
{
    if(sum>len){ len=sum;st=u; }
    int i,j,v;
    for(i=head[u];i;i=edge[i].next)
    {
        v=edge[i].v;
        if(v!=fa)
        {
            dfs(v,u,sum+edge[i].w);
        }
    }
}
void dfs1(int u,int fa,int k,int sum)
{
    dist[u][k]=sum;
    int i,j,v;
    for(i=head[u];i;i=edge[i].next)
    {
        v=edge[i].v;
        if(v!=fa) dfs1(v,u,k,sum+edge[i].w);
    }
}
void init_rmq()              // 預處理  O(n*log(n))
{
    int i,j;
    for(i=1;i<=n;i++)
    {
        f[i][0]=g[i][0]=val[i];
    }
    for(j=1;(1<>1]+1;
    }
    while(~scanf("%d%d",&n,&m))
    {
        if(n==0&&m==0) break ;
        cnt=0;
        memset(head,0,sizeof(head));
        int u,v,w;
        for(i=1;iq) id++;
                    else break ;
                }
                ans=max(ans,i-id+1);
            }
            printf("%d\n",ans);
        }
    }
    return 0;
}