CF1583H Solution

link

第一问容易处理，将边权从大到小排序，并查集维护一下连通块最大值简单搞搞就好。

考虑第二问。我们对原树，按照 \(t\) 的权值建造克鲁斯卡尔重构树，那么两点的 lca 权值即它们路径上边权最大值。

同样按照边权 \(c\) 从大到小将边排序，维护连通块内最大值的同时，维护等于最大值的点的重构树上 dfn 最大最小值。

由于重构树是一个大根堆，我们要找 \(v\) 让 \(u,v\) 的 lca 权值最大，一个结论是让 \(u,v\) 的 dfn 差值最大。

所以 \(v\) 要么是 dfn 最大的点要么是最小的点。把它们分别和 \(u\) 的 lca 权值求出来取 max 就是第二问的答案。

复杂度线性对数，瓶颈在于 lca。