原文地址：http://www.cnblogs.com/GXZlegend/p/6825389.html
题目描述
小T与小L终于决定走在一起,他们不想浪费在一起的每一分每一秒,所以他们决定每天早上一同晨练来享受在一起的时光.
他们画出了晨练路线的草图,眼尖的小T发现可以用树来描绘这个草图.
他们不愿枯燥的每天从同一个地方开始他们的锻炼,所以他们准备给起点标号后顺序地从每个起点开始(第一天从起点一开始,第二天从起点二开始……). 而且他们给每条道路定上一个幸福的值.很显然他们每次出发都想走幸福值和最长的路线(即从起点到树上的某一点路径中最长的一条).
他们不愿再经历之前的大起大落,所以决定连续几天的幸福值波动不能超过M(即一段连续的区间并且区间的最大值最小值之差不超过M).他们想知道要是这样的话他们最多能连续锻炼多少天(hint:不一定从第一天一直开始连续锻炼)?
现在，他们把这个艰巨的任务交给你了!
输入
第一行包含两个整数N, M(M<=10^9).
第二至第N行,每行两个数字Fi , Di, 第i行表示第i个节点的父亲是Fi,且道路的幸福值是Di.
输出
最长的连续锻炼天数
样例输入
3 2 1 1 1 3
样例输出
3
题解
树形dp+倍增RMQ+二分，这完全是两道题拼成一道题的啊。。。
先用树形dp求出到某个点最大距离。
设fst[x]表示以x为根的树中点到x的最大距离，fnd[x]表示以x为根的树中，除去fst[x]所在子树以外其余子树中的点到x的最大距离。
这里比较难想，待会分析。
第一次dfs可以直接处理好deep、fst和fnd。
然后考虑如何用x递推出x的儿子y的最远距离。
那么对于y，有2种情况可能构成到y距离最大：在y的父树中、在y的子树中，在y的父树中包括在x的父树中和在x除y以外的子树中。
在y的子树中即为fst[y]，在x除y以外的子树中，需要判断y是否为构成到点x的最大距离的点所在的子树：如果是fst则取fnd，否则取fst。
这样就能够dp求出到某个点最大距离。
然后对于每个点，二分后边的位置，RMQ预处理，O(1)求出区间极差，判断一下即可。
#include#include using namespace std;int head[1000010] , to[2000010] , next[2000010] , cnt , n , k , p , q;int len[2000010] , fst[1000010] , fnd[1000010] , ff[1000010] , deep[1000010] , minn[1000010][22] , maxn[1000010][22] , log[1000010];void add(int x , int y , int z){ to[++cnt] = y , len[cnt] = z , next[cnt] = head[x] , head[x] = cnt;}void dfs1(int x , int fa){ int i , y; for(i = head[x] ; i ; i = next[i]) { y = to[i]; if(y != fa) { deep[y] = deep[x] + len[i]; dfs1(y , x); if(fst[y] + len[i] > fst[x]) fnd[x] = fst[x] , fst[x] = fst[y] + len[i]; else if(fst[y] + len[i] > fnd[x]) fnd[x] = fst[y] + len[i]; } }}void dfs2(int x , int fa){ int i , y; for(i = head[x] ; i ; i = next[i]) { y = to[i]; if(y != fa) { if(fst[x] - len[i] == fst[y]) ff[y] = max(ff[x] + len[i] , fnd[x] + len[i]); else ff[y] = max(ff[x] + len[i] , fst[x] + len[i]); dfs2(y , x); } }}int getsub(int l , int r){ int k = log[r - l + 1]; return max(maxn[l][k] , maxn[r - (1 << k) + 1][k]) - min(minn[l][k] , minn[r - (1 << k) + 1][k]);}int find(int t){ int l = t , r = n , mid , ans; while(l <= r) { mid = (l + r) >> 1; if(getsub(t , mid) <= k) ans = mid , l = mid + 1; else r = mid - 1; } return ans;}int main(){ int i , j , x , y , ans = -1; scanf("%d%d" , &n , &k); for(i = 2 ; i <= n ; i ++ ) scanf("%d%d" , &x , &y) , add(i , x , y) , add(x , i , y); dfs1(1 , 0) , dfs2(1 , 0); for(i = 1 ; i <= n ; i ++ ) maxn[i][0] = minn[i][0] = max(ff[i] , fst[i]); for(i = 2 ; i <= n ; i ++ ) log[i] = log[i >> 1] + 1; for(i = 1 ; i <= log[n] ; i ++ ) for(j = 1 ; j <= n - (1 << i) + 1 ; j ++ ) maxn[j][i] = max(maxn[j][i - 1] , maxn[j + (1 << (i - 1))][i - 1]) , minn[j][i] = min(minn[j][i - 1] , minn[j + (1 << (i - 1))][i - 1]); for(i = 1 ; i <= n - p + 1 ; i ++ ) x = find(i) , ans = max(ans , find(i) - i + 1); printf("%d\n" , ans); return 0;}