• 2024-07-19P3206 城市建设 题解
    Statement动态边权的最小生成树。\(n\le2\cdot10^4,m,q\le5\cdot10^4\)Solution法一:改边权相当于删一条边再加一条边.考虑LCT维护最小生成树,加边好做,但删边比较麻烦,于是采用线段树分治,撤销一条边是好做的,cut再link一下就行了.\(O(n\logn\logq)\),常数较大.法二:两个结