POJ-3162 Walking Race (求树上两点之间最大距离)

时间:2021-12-23 15:27:11

题目大意:给一棵树,对于所有的点,找出距它最远点的距离,然后将这些距离排成一列,找出最长的一个区间满足:其中的最大值减去最小值不大于m。

题目分析:两次dfs找出距每个节点的最远距离,然后可以通过维护两个单调队列来找最长区间,也可以通过线段树区间合并来找,后者比较麻烦。

代码如下:

# include<iostream>
# include<cstdio>
# include<cstring>
# include<vector>
# include<queue>
# include<list>
# include<set>
# include<map>
# include<string>
# include<cmath>
# include<cstdlib>
# include<algorithm>
using namespace std;
# define LL long long const int N=1005;
const int INF=1000000000; ////////////////////////////////////////////
struct Edge
{
int to,w,nxt;
};
Edge e[N*N*2];
int maxn[N*N];
int rmaxn[N*N];
int maxid[N*N];
int rmaxid[N*N];
int n,m,cnt;
int head[N*N]; void add(int u,int v,int w)
{
e[cnt].to=v;
e[cnt].w=w;
e[cnt].nxt=head[u];
head[u]=cnt++;
} void init()
{
cnt=0;
memset(head,-1,sizeof(head));
int a,b;
for(int i=2;i<=n;++i){
scanf("%d%d",&a,&b);
add(i,a,b);
add(a,i,b);
}
} void dfs1(int u,int fa)
{
maxn[u]=rmaxn[u]=0;
for(int i=head[u];i!=-1;i=e[i].nxt){
int v=e[i].to;
if(v==fa) continue;
dfs1(v,u);
if(e[i].w+maxn[v]>rmaxn[u]){
rmaxn[u]=e[i].w+maxn[v];
rmaxid[u]=v;
if(rmaxn[u]>maxn[u]){
swap(rmaxn[u],maxn[u]);
swap(rmaxid[u],maxid[u]);
}
}
}
} void dfs2(int u,int fa)
{
for(int i=head[u];i!=-1;i=e[i].nxt){
int v=e[i].to;
if(v==fa) continue;
if(v==maxid[u]){
if(rmaxn[u]+e[i].w>rmaxn[v]){
rmaxn[v]=rmaxn[u]+e[i].w;
rmaxid[v]=u;
if(rmaxn[v]>maxn[v]){
swap(rmaxn[v],maxn[v]);
swap(rmaxid[v],maxid[v]);
}
}
}else{
if(maxn[u]+e[i].w>rmaxn[v]){
rmaxn[v]=maxn[u]+e[i].w;
rmaxid[v]=u;
if(rmaxn[v]>maxn[v]){
swap(rmaxn[v],maxn[v]);
swap(rmaxid[v],maxid[v]);
}
}
}
dfs2(v,u);
}
} void getDp()
{
dfs1(1,-1);
dfs2(1,-1);
}
//////////////////////////////////////////// int qmax[N*N];
int qmin[N*N]; void solve()
{
int ans=0;
int head1=0,tail1=-1;
int head2=0,tail2=-1;
int l=1,r=1;
while(r<=n){
while(head1<=tail1&&maxn[r]>=maxn[qmax[tail1]]) --tail1;
qmax[++tail1]=r;
while(head2<=tail2&&maxn[r]<=maxn[qmin[tail2]]) --tail2;
qmin[++tail2]=r;
if(maxn[qmax[head1]]-maxn[qmin[head2]]>m){
ans=max(ans,r-l);
while(maxn[qmax[head1]]-maxn[qmin[head2]]>m){
l=min(qmax[head1],qmin[head2])+1;
while(head1<=tail1&&qmax[head1]<l) ++head1;
while(head2<=tail2&&qmin[head2]<l) ++head2;
}
}
++r;
}
ans=max(ans,r-l);
printf("%d\n",ans);
} int main()
{
while(~scanf("%d%d",&n,&m))
{
init();
getDp();
solve();
}
return 0;
}