POJ 3162 Walking Race 树形dp 优先队列

题意 : 一棵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 ;

 }

巴特西

POJ 3162 Walking Race 树形dp 优先队列

最新文章

热门文章