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