poj 3162 线段树 hdu 4123 bfs + RMQ预处理
题意：给你一棵树，然后标号为1~n，每条边都有一定的边权，那么从每个点出发都有一个最远距离num[i];
先求出num【】数组，然后再有500个询问，每个询问输入一个整数m，求num数组中最大值与最小值绝对值之差不超过m的最长的连续区间是多少。
这是2011福州区域赛的题目，咋一看蛮难的，其实是个大水题，poj也有类似的题目，应该说是改编过来的吧。
好了，讲讲我是怎么做的吧
1：利用树的最长路的结论我们首先预处理出num数组
2：由于后面需要查询区间最值，所以先用RMQ预处理num【】，后面查询的时候就可以做到O(1)查询，如果用线段树的话复杂度会太大
3：对于每个询问，可以做到O(n)回答，维护两个指针l,r 如果当前区间满足条件r++,否则l++，每个点都易做图入删除一次，区间最值的查询是O(1）的，所以询问的复杂度是
q*n即500*50000.
总复杂度是nlog(n)+q*n
所以就是q*n的复杂度，即500*50000，时限两秒，小轻松啊~
[cpp]
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int inf = ~0u>>2;
const int maxn = 50010;
int n,m;
struct Edge{
int v,w,next;
}edge[2*maxn];
int head[maxn],E,num[maxn];
void add_edge(int a,int b,int w)
{
edge[E].v=b;
edge[E].w=w;
edge[E].next=head[a];
head[a]=E++;
}
int dis1[maxn],dis2[maxn];
bool vis[maxn];
int q[maxn];
void bfs(int s,int &ss,int dist[]) {
fill(dist,dist+n+1,inf);
fill(vis,vis+n+1,false);
vis[s]=true;
dist[s]=0;
int front(0),tail(0),u,v,w;
q[0]=s;int Max=0;
while(front<=tail) {
u=q[front++];
for(int i=head[u];i!=-1;i=edge[i].next) {
v=edge[i].v,w=edge[i].w;
if(vis[v]) continue;
vis[v]=true;
dist[v]=dist[u]+w;
if(dist[v]>Max) {
Max=dist[v];
ss=v;
}
q[++tail]=v;
}
}
}
int LOG[2*maxn];
int dp1[20][2*maxn];
int dp2[20][2*maxn];
inline int min(int a,int b){
return a<b?a:b;
}
inline int max(int a,int b){
return a>b?a:b;
}
void rmq_init(int n)
{
int i,j;
for(j=1;j<=n;j++) {
dp1[0][j]=num[j];
dp2[0][j]=num[j];
}
for(j=1;j<=LOG[n];j++) {
int limit=n+1-(1<<j);
for(i=1;i<=limit;i++) {
int x=i+(1<<j>>1);
dp1[j][i]=min(dp1[j-1][x],dp1[j-1][i]);
dp2[j][i]=max(dp2[j-1][x],dp2[j-1][i]);
}
}
}
int rmq_min(int l,int r)
{
int m=LOG[r-l+1];
return min(dp1[m][l],dp1[m][r-(1<<m)+1]);
}
int rmq_max(int l,int r)
{
int m=LOG[r-l+1];
return max(dp2[m][l],dp2[m][r-(1<<m)+1]);
}
int main()
{
int q;
LOG[0]=-1;
for(int i=1;i<2*maxn;i++) LOG[i]=LOG[i>>1]+1;
while(scanf("%d%d",&n,&q),n||q)
{
E=0;fill(head,head+n+1,-1);
for(int i=2,a,b,w;i<=n;i++)
{
scanf("%d%d%d",&a,&b,&w);
add_edge(a,b,w);
add_edge(b,a,w);
}
int ss,tt;
bfs(1,ss,dis1);
bfs(ss,tt,dis1);
bfs(tt,ss,dis2);
for(int i=1;i<=n;i++) num[i]=max(dis1[i],dis2[i]);
rmq_init(n);
while(q--) {
scanf("%d",&m);
int ans=0;
int l=1,r=1,mx,mi;
while(r<=n) {
mx=rmq_max(l,r);
mi=rmq_min(l,r);
if(mx-mi<=m) {
ans=max(ans,r-l+1);
r++;
}
else l++;
}
printf("%d\n",ans);
}
} <
补充：软件开发 , C++ ,
