当前位置：网站首页>F-niu Mei's apple tree (diameter combined)

F-niu Mei's apple tree (diameter combined)

2022-04-23 09:42:00 【Zimba_】

Topic link

The question ：

A tree n n n A tree of nodes , Each edge has an edge weight w i wi wi. Yes q q q Time to ask , Every time I ask l l l and r r r, seek 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)

practice ：

Here's a conclusion ： The diameter endpoints of two subgraphs are known , Then the diameter of the merged two graphs , Take the farthest two of these four points .
So this problem is considered to be multiplied to deal with ST surface . You need to merge the maximum values of the two intervals , Just save the diameter endpoint of each interval , You can merge to get a new diameter .

Code ：

 The solution is so simple , Code YY Just a moment .

版权声明
本文为[Zimba_]所创，转载请带上原文链接，感谢
https://yzsam.com/2022/04/202204230621425179.html

边栏推荐

猜你喜欢

随机推荐