图论,数据结构

题意每个点有各自的权值，要求维护操作：动态加边、动态修改权值、询问在每个点只能经过一次的情况下两点间路程中的最大权值和 题解首先对于一个静态的图，将其缩点，可以得到一棵树，那么两点间询问的答案即为它们之间经过的 $BCC$ 的权值和 支持动态加边，就需要用到 $LCT$ 去维护 $BCC$ 如果两个点所在 $BCC$ 在不同树上，那么直接连边即可；反之，则说明形成了环，就暴力将这条链拖出来，用选定一个标准节点，用并查集将链上其它节点连到标准节点上，容易证明，这样的复杂度是均摊 $O (\log n)$ 的 查询即修改容易实现，不加赘述 注意，此题没有删边，所以 $findroot$ 可用另一个并查集代替，不然会 $T$ 代码1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586878889909192939495969 ...