本文主要是介绍bzoj 2500 幸福的道路 树上直径+set，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
首先明确：树上任意一点的最长路径一定是直径的某一端点。
所以先找出直径，求出最长路径，然后再求波动值<=m的最长区间
#include<cstdio>
#include<cstring>
#include<iostream>
#include<cmath>
#include<algorithm>
#include<ctime>
#include<set>
#define N 1000005
using namespace std;int fa[N],cal[N],dis[2][N],d[N]; int e=1,head[N];struct edge{int u,v,w,next;
}ed[N];void add(int u,int v,int w){ed[e].u=u; ed[e].v=v; ed[e].w=w;ed[e].next=head[u]; head[u]=e++;
}int L,R,it,maxn;bool bo[N];void dfs(int x,int len){bo[x]=1; if(len>maxn) it=x,maxn=len;if(!bo[fa[x]]) dfs(fa[x],len+cal[x]);for(int i=head[x];i;i=ed[i].next){if(!bo[ed[i].v])dfs(ed[i].v,len+ed[i].w);}
}int q[N],h,t;void bfs(int x,int wh){bo[x]=1;int now,v,w; dis[wh][x]=0;q[1]=x; h=t=1;while(h<=t){now=q[h++];if(fa[now]&&!bo[fa[now]]&&dis[wh][fa[now]]<dis[wh][now]+cal[now]){dis[wh][fa[now]]=dis[wh][now]+cal[now];bo[fa[now]]=1; q[++t]=fa[now];}for(int i=head[now];i;i=ed[i].next){v=ed[i].v; w=ed[i].w;if(!bo[v]&&dis[wh][v]<dis[wh][now]+w){dis[wh][v]=dis[wh][now]+w;bo[v]=1; q[++t]=v;}}}
}int n,m;int main()
{ //freopen("race.in","r",stdin);//freopen("race.out","w",stdout);scanf("%d%d",&n,&m);for(int i=2;i<=n;i++){scanf("%d%d",&fa[i],&cal[i]);add(fa[i],i,cal[i]);}maxn=0; memset(bo,0,sizeof bo); dfs(1,0); L=it; maxn=0; memset(bo,0,sizeof bo); dfs(L,0); R=it;memset(bo,0,sizeof bo); bfs(L,0); memset(bo,0,sizeof bo); bfs(R,1);for(int i=1;i<=n;i++) d[i]=max(dis[0][i],dis[1][i]);//printf("%0.2lf\n",(double)clock()/CLOCKS_PER_SEC);multiset<int > ss; int dd,xx,ll=1,ans=0;for(int i=1;i<=n;i++){ss.insert(d[i]);dd=*(--ss.end());xx=*(ss.begin());while(dd-xx>m) ss.erase(ss.find(d[ll++])),dd=*(--ss.end()),xx=*(ss.begin());ans=max(ans,i-ll+1);}printf("%d\n",ans);return 0;
}这篇关于bzoj 2500 幸福的道路 树上直径+set的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
