首页 > 代码库 > BZOJ 2500 幸福的道路
BZOJ 2500 幸福的道路
题面:
2500: 幸福的道路
Time Limit: 20 Sec Memory Limit: 256 MBSubmit: 366 Solved: 144
[Submit][Status][Discuss]
Description
小T与小L终于决定走在一起,他们不想浪费在一起的每一分每一秒,所以他们决定每天早上一同晨练来享受在一起的时光.
他们画出了晨练路线的草图,眼尖的小T发现可以用树来描绘这个草图.
他们不愿枯燥的每天从同一个地方开始他们的锻炼,所以他们准备给起点标号后顺序地从每个起点开始(第一天从起点一开始,第二天从起点二开始……). 而且他们给每条道路定上一个幸福的值.很显然他们每次出发都想走幸福值和最长的路线(即从起点到树上的某一点路径中最长的一条).
他们不愿再经历之前的大起大落,所以决定连续几天的幸福值波动不能超过M(即一段连续的区间并且区间的最大值最小值之差不超过M).他们想知道要是这样的话他们最多能连续锻炼多少天(hint:不一定从第一天一直开始连续锻炼)?
现在,他们把这个艰巨的任务交给你了!
Input
第一行包含两个整数N, M(M<=10^9).
第二至第N行,每行两个数字Fi , Di, 第i行表示第i个节点的父亲是Fi,且道路的幸福值是Di.
Output
最长的连续锻炼天数
Sample Input
3 2
1 1
1 3
1 1
1 3
Sample Output
3
数据范围:
50%的数据N<=1000
80%的数据N<=100 000
100%的数据N<=1000 000
数据范围:
50%的数据N<=1000
80%的数据N<=100 000
100%的数据N<=1000 000
HINT
Source
先用两次DFS求出每个点的最长距离,再用单调队列求出最长区间。
1 #include<iostream> 2 #include<stdio.h> 3 #include<string.h> 4 using namespace std; 5 #define maxn 1000001 6 #define LL long long 7 int n,m,t=1,ans; 8 int f[maxn],dis[maxn],g[maxn]; 9 struct node 10 { 11 int u,v,w,nex; 12 }edge[maxn<<1]; 13 int head[maxn],cnt; 14 int read() 15 { 16 int x=0; 17 char ch=getchar(); 18 while(ch<‘0‘||ch>‘9‘) 19 ch=getchar(); 20 while(ch>=‘0‘&&ch<=‘9‘) 21 x=x*10+ch-‘0‘,ch=getchar(); 22 return x; 23 } 24 void add(int u,int v,int w) 25 { 26 edge[++cnt]=(node){u,v,w,head[u]}; 27 head[u]=cnt; 28 } 29 void dfs1(int u,int fa) 30 { 31 int v; 32 for(int i=head[u];i;i=edge[i].nex) 33 { 34 v=edge[i].v; 35 if(v!=fa) 36 { 37 dfs1(v,u); 38 f[u]=max(f[u],f[v]+edge[i].w); 39 } 40 } 41 } 42 void dfs2(int u,int fa) 43 { 44 int v; 45 int max1=0,max2=0; 46 for(int i=head[u];i;i=edge[i].nex) 47 { 48 v=edge[i].v; 49 if(v!=fa) 50 { 51 if(f[v]+edge[i].w>max1) 52 max2=max1,max1=f[v]+edge[i].w; 53 else 54 max2=max(max2,f[v]+edge[i].w); 55 g[v]=g[u]+edge[i].w; 56 } 57 } 58 for(int i=head[u];i;i=edge[i].nex) 59 { 60 v=edge[i].v; 61 if(v!=fa) 62 { 63 if(f[v]+edge[i].w==max1) 64 g[v]=max(g[v],edge[i].w+max2); 65 else 66 g[v]=max(g[v],edge[i].w+max1); 67 dfs2(v,u); 68 } 69 } 70 } 71 class de 72 { 73 private: 74 int head,tail; 75 int q[maxn]; 76 public: 77 de() 78 { 79 head=1;tail=0; 80 memset(q,0,sizeof(q)); 81 } 82 void pushup(int x) 83 { 84 while(head<=tail&&dis[q[tail]]>=dis[x]) 85 --tail; 86 q[++tail]=x; 87 } 88 void pushdown(int x) 89 { 90 while(head<=tail&&dis[q[tail]]<=dis[x]) 91 --tail; 92 q[++tail]=x; 93 } 94 bool emp(){return (head<=tail);} 95 void pp(){++head;} 96 int tp(){return q[head];} 97 }q1,q2; 98 int main() 99 { 100 int x,y; 101 n=read(); 102 m=read(); 103 for(int i=2;i<=n;i++) 104 { 105 x=read(); 106 y=read(); 107 add(x,i,y); 108 add(i,x,y); 109 } 110 dfs1(1,0); 111 dfs2(1,0); 112 for(int i=1;i<=n;i++) 113 { 114 dis[i]=max(g[i],f[i]); 115 q1.pushup(i); 116 q2.pushdown(i); 117 while(dis[q2.tp()]-dis[q1.tp()]>m) 118 { 119 if(q2.tp()<=q1.tp()) 120 t=q2.tp()+1,q2.pp(); 121 else 122 t=q1.tp()+1,q1.pp(); 123 } 124 ans=max(ans,i-t+1); 125 } 126 printf("%d",ans); 127 }
BZOJ 2500 幸福的道路
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。