題意：給你一棵樹，然後標號為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);
}
}
return 0;
}
http://poj.org/problem?id=3162
poj 3162這題呢有100W個點啊，RMQ的話空間開不下，所以只能線段樹查詢區間最值了，復雜度n*log(n),discuss說還有O(n)的做法，好像是單調隊列的做法，還不會，等會了再貼上來吧。
c++跑了5 S 多
[cpp]
#include<cstdio>
#include<set>
#include<cstring>
#include<algorithm>
using namespace std;
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
const int inf = ~0u>>2;
const int maxn = 1000010;
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;
}
}
}
inline int min(int a,int b){
return a<b?a:b;
}
inline int max(int a,int b){
return a>b?a:b;
}
int mx[maxn<<2],mi[maxn<<2];
void pushup(int rt){
mx[rt]=max(mx[rt<<1],mx[rt<<1|1]);
mi[rt]=min(mi[rt<<1],mi[rt<<1|1]);
}
void build(int l,int r,int rt){
if(l==r){
mx[rt]=mi[rt]=num[l];
return ;
}
int m=(l+r)>>1;
build(lson);
build(rson);
pushup(rt);
}
int find_min(int L,int R,int l,int r,int rt)
{
if(L<=l&&r<=R)
{
return mi[rt];
}
int m=(l+r)>>1;
int ret=inf;
if(L<=m) ret=min(ret,find_min(L,R,lson));
if(R>m) ret=min(ret,find_min(L,R,rson));
return ret;
}
int find_max(int L,int R,int l,int r,int rt)
{
if(L<=l&&r<=R)
{
return mx[rt];
}
int m=l+r>>1;
int ret=0;
if(L<=m) ret=max(ret,find_max(L,R,lson));
if(R>m) ret=max(ret,find_max(L,R,rson));
return ret;
}
int main()
{
scanf("%d%d",&n,&m);
E=0;fill(head,head+n+1,-1);
for(int i=2,fa,w;i<=n;i++)
{
scanf("%d%d",&fa,&w);
add_edge(i,fa,w);
add_edge(fa,i,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]);
}
int l=1,r=1,mx,mi;
int ans=0;
build(1,n,1);
while(r<=n)
{
mx=find_max(l,r,1,n,1);
mi=find_min(l,r,1,n,1);
if(mx-mi<=m)
{
ans=max(ans,r-l+1);
r++;
}
else {
l++;
}
}
printf("%d\n",ans);
return 0;
}
