给出一棵树，编号为1~n,给出数m
漂亮mm连续n天锻炼身体，每天会以节点i为起点，走到离i最远距离的节点
走了n天之后，mm想到知道自己这n天的锻炼效果
于是mm把这n天每一天走的距离记录在一起，成为一段长度为n的数列
现在mm想要从这数列中选出一个连续的区间，要求这个区间的max-min<=m
输出最长的区间
做了一个下午
思路：
分成2个部分：
1.求出数列，即对于一棵树，求出每一个节点能到达的最远距离
2.对于这段数列，选出一个区间，使得区间的max-min<=m，并且使得区间长度尽量长。
对于第1部分，其实就是我昨天做的题目，HDU2196，使用树形DP
dp[i][1]:表示从i出发到i的子树，能到达的最远距离
dp[i][2]:表示从i出发到i的子树，能到达的第二远的距离(求dp[i][0]的时候需要用到)
dp[i][0]:表示从i出发，经过i的父亲节点，能到达的最远距离
4次dfs，分别求出：
0.节点的depth，以便把边权(u,v)转化为u,v中depth较大的节点的点权，cost[root]=0;
1.求出dp[i][1]和son[i],son[i]表示dp[i][1]是通过子节点son[i]这道路径得到的
2.求出dp[i][2]
3.求出dp[i][0]
完成第一部分
第二部分，前段时间也做过类似的题，HDU5289
5289要求的是数列中有多少个区间满足条件，我是用RMQ+二分
这道求的是满足条件的最长区间长度
我主要时间是花在了解决第二部分
我刚开始也是用RMQ+二分
发现mle了
因为5289的长度n<=1e5,而这道，n<=1e6，所以RMQ开了会mle
然后我就想改为用线段树代替RMQ的作用，用线段树维护区间的最大值和最小值也很方便，还可以省下很多空间
然后，tle了
原因：
这道题和5289不同的是，这道题不用枚举每一个区间，判断到底满不满足要求
只要求出一个满足的最长的就好啦
然后把枚举左端点+二分右端点的代码注释了
换了种方式：
用2个指针l，r，
若区间[l,r]满足条件，r++，同时更新答案
若不满足条件，l++，直到[l,r]满足条件
复杂度O(n)
这就是传说中的尺取法？
这过程我还犯了一个及其严重的错误:
求最大值的时候，没有把max_ret初始化为-inf
求最小值的时候，没有把min_ret初始化为inf
又花了不少时间
然后终于过了
1 #include<cstdio> 2 #include<cstring> 3 4 using namespace std; 5 #define lson l,m,rt<<1 6 #define rson m+1,r,rt<<1|1 7 8 inline int max(int a,int b) 9 { 10 return a>b?a:b; 11 } 12 13 inline int min(int a,int b) 14 { 15 return a<b?a:b; 16 } 17 18 const int maxn=1e6+5; 19 const int inf=0x3f3f3f3f; 20 21 struct Edge 22 { 23 int to,next; 24 }; 25 Edge edge[maxn<<1]; 26 int head[maxn]; 27 int tot; 28 int son[maxn]; 29 int dp[maxn][3]; 30 int e[maxn][2]; 31 int dep[maxn]; 32 int cost[maxn]; 33 int seg_max[maxn<<2]; 34 int seg_min[maxn<<2]; 35 int max_ret; 36 int min_ret; 37 38 void init() 39 { 40 memset(head,-1,sizeof head); 41 tot=1; 42 memset(dep,0,sizeof dep); 43 memset(dp,0,sizeof dp); 44 memset(son,-1,sizeof son); 45 } 46 47 void addedge(int u,int v) 48 { 49 edge[tot].to=v; 50 edge[tot].next=head[u]; 51 head[u]=tot++; 52 } 53 54 void solve(int n,int m); 55 void dfs0(int u,int pre); 56 void dfs1(int u,int pre); 57 void dfs2(int u,int pre); 58 void dfs3(int u,int pre); 59 void build(int l,int r,int rt); 60 void pushup(int rt); 61 int query(int L,int R,int n); 62 void query_ret(int L,int R,int l,int r,int rt); 63 64 int main() 65 { 66 int n,m; 67 while(~scanf("%d %d",&n,&m)) 68 { 69 init(); 70 for(int i=2;i<=n;i++) 71 { 72 int u,v; 73 scanf("%d %d",&e[i][0],&e[i][1]); 74 addedge(i,e[i][0]); 75 addedge(e[i][0],i); 76 } 77 solve(n,m); 78 } 79 return 0; 80 } 81 82 void solve(int n,int m) 83 { 84 dfs0(1,-1); 85 cost[1]=0; 86 for(int i=2;i<=n;i++) 87 { 88 if(dep[i]>dep[e[i][0]]) 89 cost[i]=e[i][1]; 90 else 91 cost[e[i][0]]=e[i][1]; 92 } 93 dfs1(1,-1); 94 dfs2(1,-1); 95 dfs3(1,-1); 96 build(1,n,1); 97 /* 98 for(int i=1;i<=n;i++) 99 { 100 printf("%d ",max(dp[i][0],dp[i][1])); 101 } 102 */ 103 /* 104 int ans=0; 105 for(int i=1;i<=n;i++) 106 { 107 int l=i,r=n; 108 while(r-l>1) 109 { 110 int mid=(l+r)>>1; 111 if(query(i,mid,n)>m) 112 r=mid; 113 else 114 l=mid; 115 } 116 if(query(i,r,n)<=m) 117 ans=max(ans,r-i+1); 118 else 119 ans=max(ans,l-i+1); 120 } 121 */ 122 123 int ans=0; 124 int l=1,r=1; 125 while(r<=n) 126 { 127 while(l<=r&&query(l,r,n)>m) 128 { 129 l++; 130 } 131 while(r<=n&&query(l,r,n)<=m) 132 { 133 ans=max(ans,r-l+1); 134 r++; 135 } 136 } 137 138 printf("%d ",ans); 139 return ; 140 } 141 142 void dfs0(int u,int pre) 143 { 144 for(int i=head[u];~i;i=edge[i].next) 145 { 146 int v=edge[i].to; 147 if(v==pre) 148 continue; 149 dep[v]=dep[u]+1; 150 dfs0(v,u); 151 } 152 } 153 154 void dfs1(int u,int pre) 155 { 156 for(int i=head[u];~i;i=edge[i].next) 157 { 158 int v=edge[i].to; 159 if(v==pre) 160 continue; 161 dfs1(v,u); 162 if(dp[v][1]+cost[v]>dp[u][1]) 163 { 164 dp[u][1]=dp[v][1]+cost[v]; 165 son[u]=v; 166 } 167 } 168 } 169 170 void dfs2(int u,int pre) 171 { 172 for(int i=head[u];~i;i=edge[i].next) 173 { 174 int v=edge[i].to; 175 if(v==pre) 176 continue; 177 dfs2(v,u); 178 if(v==son[u]) 179 continue; 180 if(dp[v][1]+cost[v]>dp[u][2]) 181 { 182 dp[u][2]=dp[v][1]+cost[v]; 183 } 184 } 185 } 186 187 void dfs3(int u,int pre) 188 { 189 for(int i=head[u];~i;i=edge[i].next) 190 { 191 int v=edge[i].to; 192 if(v==pre) 193 continue; 194 if(v==son[u]) 195 { 196 dp[v][0]=max(dp[u][0],dp[u][2])+cost[v]; 197 } 198 else 199 { 200 dp[v][0]=max(dp[u][0],dp[u][1])+cost[v]; 201 } 202 dfs3(v,u); 203 } 204 } 205 206 void pushup(int rt) 207 { 208 seg_max[rt]=max(seg_max[rt<<1],seg_max[rt<<1|1]); 209 seg_min[rt]=min(seg_min[rt<<1],seg_min[rt<<1|1]); 210 } 211 212 void build(int l,int r,int rt) 213 { 214 if(l==r) 215 { 216 seg_max[rt]=seg_min[rt]=max(dp[l][0],dp[l][1]); 217 return ; 218 } 219 int m=(l+r)>>1; 220 build(lson); 221 build(rson); 222 pushup(rt); 223 } 224 225 int query(int L,int R,int n) 226 { 227 max_ret=-inf; 228 min_ret=inf; 229 query_ret(L,R,1,n,1); 230 return max_ret-min_ret; 231 } 232 233 void query_ret(int L,int R,int l,int r,int rt) 234 { 235 if(L<=l&&R>=r) 236 { 237 max_ret=max(max_ret,seg_max[rt]); 238 min_ret=min(min_ret,seg_min[rt]); 239 return ; 240 } 241 int m=(l+r)>>1; 242 if(L<=m) 243 query_ret(L,R,lson); 244 if(R>m) 245 query_ret(L,R,rson); 246 }