GDOI2015小Z的旅行路线

GDOI2015小Z的旅行路线

题意:

(n)个点的无根树,边上有权值。
(q)个询问(s)(s),问从(s)出发,找一条最长路(不经过重复点),保证路径上所有边边权不超过(x)

说明:

(N le 100000)


不知道这个题在哪做,但思路值得说一下

保留原树

对询问树,以(x)为关键字排序询问,顺序加边。

对每个连通块维护直径

每次加边时如果有两个连通块,2*2暴力更新直径的端点(原来直径上的四个端点一定有两个是新直径的两个端点)

比较长度时在原树上做倍增(LCA)即可

询问最长路直接询问此点在当前连通块的直径两端的距离

复杂度:(O(nlogn))

代码没写QAQ

原文地址:https://www.cnblogs.com/butterflydew/p/9340135.html