当前位置：网站首页>F-牛妹的苹果树（直径合并）

F-牛妹的苹果树（直径合并）

2022-04-23 06:21:00 【Zimba_】

题目链接

题意：

一棵 n n n个结点的树，每条边有个边权 w i wi wi。有 q q q次询问，每次询问 l l l和 r r r，求 m a x ( d i s t ( u , v ) ) , l ≤ u ≤ v ≤ r max(dist(u,v)),l\leq u\leq v\leq r max(dist(u,v)),l≤u≤v≤r。
( 1 ≤ n , q ≤ 300000 ) (1\leq n,q\leq 300000) (1≤n,q≤300000)

做法：

这里有一个结论：已知两个子图的直径端点，那么两个图合并后的直径，就在这四个点中取最远的两个点。
所以这题考虑倍增处理出ST表。需要两个区间的最值合并，只要保存每个区间的直径端点，就可以合并得到新的直径了。

代码：

题解这么简单，代码YY一下就好了。

版权声明
本文为[Zimba_]所创，转载请带上原文链接，感谢
https://blog.csdn.net/weixin_43785386/article/details/108027552

边栏推荐

猜你喜欢

随机推荐