Bob’s Race
Time Limit: 20 Sec
Memory Limit: 256 MB
题目连接
http://acm.hdu.edu.cn/showproblem.php?pid=4123
Description
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
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
HINT
题意
一个城镇有N个住户，N-1条路连接两个住户，保证N个住户联通，M次询问，给定N条边的信息，包括连
接的住户序号以及路的长度。然后是M次询问，每次询问Q，要求找到最长的连续序号，使得Max(dis[i]) - Min(dis[i]) ≤
Q(l≤i≤r)，输出最大的r-l+1。dis[i]为从第i个住户出发，不重复走过路能移动的最远距离。
题解：
dis[i]一定是点到直径的某个点的距离，所以我们两次dfs求出直径，然后两次dfs求出距离就好了
至于第二问，对于每个询问，我们可以O(N)扫一遍就好了
代码
#include<iostream>
#include<stdio.h>
#include<cstring>
#include<vector>
using namespace std; vector<pair<int,int> > Q[];
int d[];
int n,m;
int left1,l_num;
int Right,r_num;
int dpMax[][], dpMin[][];
void dfs1(int x,int pre,int len,int type)
{
if(type == && l_num < len)
{
l_num = len;
left1 = x;
}
if(type == && r_num < len)
{
r_num = len;
Right = x;
}
for(int i=;i<Q[x].size();i++)
{
pair<int,int> K = Q[x][i];
if(K.first == pre)continue;
dfs1(K.first,x,len + K.second,type);
}
}
void dfs2(int x,int pre,int len)
{
d[x]=max(d[x],len);
for(int i=;i<Q[x].size();i++)
{
pair<int,int> K = Q[x][i];
if(K.first == pre)continue;
dfs2(K.first,x,len + K.second);
}
}
void rmq_init() {
for (int i = ; i <= n; i++)
dpMax[i][] = dpMin[i][] = d[i]; for (int k = ; (<<k) <= n; k++) {
for (int i = ; i + (<<k) - <= n; i++) {
dpMax[i][k] = max(dpMax[i][k-], dpMax[i+(<<(k-))][k-]);
dpMin[i][k] = min(dpMin[i][k-], dpMin[i+(<<(k-))][k-]);
}
}
} int rmq_query(int l, int r) {
int k = ;
while ((<<(k+)) <= r - l + ) k++;
return max(dpMax[l][k], dpMax[r-(<<k)+][k]) - min(dpMin[l][k], dpMin[r-(<<k)+][k]);
}
int main()
{
while(scanf("%d%d",&n,&m)!=EOF)
{
if(n==&&m==)break;
memset(d,,sizeof(d));
memset(dpMax,,sizeof(dpMax));
memset(dpMin,,sizeof(dpMin));
for(int i=;i<=n;i++)
Q[i].clear();
for(int i=;i<n;i++)
{
int x,y,z;
scanf("%d%d%d",&x,&y,&z);
Q[x].push_back(make_pair(y,z));
Q[y].push_back(make_pair(x,z));
}
left1 = l_num = Right = r_num = ; dfs1(,-,,);
dfs1(left1,-,,);
dfs2(left1,-,);
dfs2(Right,-,);
rmq_init();
while (m--) {
int ans = , mv = ;
int QQ;
scanf("%d", &QQ);
for (int i = ; i <= n; i++) {
while (mv <= i && rmq_query(mv , i) > QQ) mv++;
ans = max(ans, i - mv + );
}
printf("%d\n", ans);
} }
}