题意 :  一棵n个节点的树。wc爱跑步,跑n天,第i天从第i个节点开始跑步,每次跑到距第i个节点最远的那个节点(产生了n个距离),现在要在这n个距离里取连续的若干天,使得这些天里最大距离和最小距离的差小于M,问怎么取使得天数最多?

 
每个点的最大距离和之前http://acm.hdu.edu.cn/showproblem.php?pid=2196这道题一样
(就是求每个子树的最长子链,次长子链,然后求经过父亲节点能达到的最大值,比较一下)
 
嗯求最长连续天数这个显然n^2是不现实的,但是连续什么的会想起很久以前似曾相识的一道优先队列题...然后强行一个大根堆一个小根堆,l和r适当情况下右移,复杂度n就可以a了...
 #include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<queue>
using namespace std;
#define pa pair<long long,int>
const int maxn=;
int n,m;
priority_queue< pa,vector< pa >,less< pa > >q1;
priority_queue< pa,vector< pa >,greater< pa > >q2;
struct nod{
int y;
long long v;
int next;
}e[maxn*];
int vis[maxn]={};
long long f[maxn][]={}; //0父亲 1最长 2次长
long long ma[maxn]={};
int f1[maxn][]={};
int head[maxn]={};
int tot=;
void init(int x,int y,long long v){
e[++tot].y=y;
e[tot].v=v;
e[tot].next=head[x];
head[x]=tot;
}
void dfs(int x){
int y;
vis[x]=;
long long tmp=;
for(int i=head[x];i;i=e[i].next){
y=e[i].y;
tmp=e[i].v;
if(!vis[y]){
dfs(y);
tmp+=f[y][];
if(tmp>f[x][]){
f[x][]=f[x][];
f1[x][]=f1[x][];
f[x][]=tmp;
f1[x][]=y;
}
else if(tmp>f[x][]){
f[x][]=tmp;
f1[x][]=y;
}
}
}
}
void dfs2(int x,int fa,long long v){
int y;
long long tmp;
vis[x]=;
if(f1[fa][]==x){
f[x][]=v+max(f[fa][],f[fa][]);
}
else{
f[x][]=v+max(f[fa][],f[fa][]);
}
ma[x]=max(f[x][],f[x][]);
for(int i=head[x];i;i=e[i].next){
y=e[i].y;
tmp=e[i].v;
if(!vis[y]){
dfs2(y,x,tmp);
}
}
}
long long mab(long long x){
if(x<){
return -x;
}
return x;
}
int main(){
scanf("%d%d",&n,&m);
int y;
long long v;
for(int i=;i<n;i++){
scanf("%d%lld",&y,&v);
init(i+,y,v);
init(y,i+,v);
}dfs();
memset(vis,,sizeof(vis));
dfs2(,,);
int ans=;
int l=,r=;
for(int i=;i<=n;i++){
q1.push(make_pair(ma[i],i));
q2.push(make_pair(ma[i],i));
r++;
int id1=q1.top().second,id2=q2.top().second;
while(id1<l){
q1.pop();
id1=q1.top().second;
}
while(id2<l){
q2.pop();
id2=q2.top().second;
}
long long z1=q1.top().first,z2=q2.top().first;
while(mab(z1-z2)>=m){
l++;
while(id1<l){
q1.pop();
id1=q1.top().second;
}
while(id2<l){
q2.pop();
id2=q2.top().second;
}
z1=q1.top().first,z2=q2.top().first;
}ans=max(ans,r-l+);
}
cout<<ans<<endl;
return ;
}
04-25 04:29
查看更多