网站营销站点有你想,如何建设公司网站,做印量调查的网站,怎么查看一个网站是哪家公司做的原文地址#xff1a;http://www.cnblogs.com/GXZlegend/p/6825389.html 题目描述 小T与小L终于决定走在一起,他们不想浪费在一起的每一分每一秒,所以他们决定每天早上一同晨练来享受在一起的时光.他们画出了晨练路线的草图,眼尖的小T发现可以用树来描绘这个草图.他们不愿枯燥的…原文地址http://www.cnblogs.com/GXZlegend/p/6825389.html 题目描述 小T与小L终于决定走在一起,他们不想浪费在一起的每一分每一秒,所以他们决定每天早上一同晨练来享受在一起的时光. 他们画出了晨练路线的草图,眼尖的小T发现可以用树来描绘这个草图. 他们不愿枯燥的每天从同一个地方开始他们的锻炼,所以他们准备给起点标号后顺序地从每个起点开始(第一天从起点一开始,第二天从起点二开始……). 而且他们给每条道路定上一个幸福的值.很显然他们每次出发都想走幸福值和最长的路线(即从起点到树上的某一点路径中最长的一条). 他们不愿再经历之前的大起大落,所以决定连续几天的幸福值波动不能超过M(即一段连续的区间并且区间的最大值最小值之差不超过M).他们想知道要是这样的话他们最多能连续锻炼多少天(hint:不一定从第一天一直开始连续锻炼)? 现在他们把这个艰巨的任务交给你了! 输入 第一行包含两个整数N, M(M10^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 cstdio
#include algorithm
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;
} 转载于:https://www.cnblogs.com/GXZlegend/p/6825389.html
