[UOJ #207] 共价大爷游长沙

UOJ #207 思路 对每个点对的两端点各赋一个点权,使得所有道路的点权不同,然后维护一下子树内的点权和,边$x, y$在所有道路上当且仅当以$x$为根时$y$的子树异或和为所有道路的权值异或和 代 […]

[NOI 2014] 魔法森林

Luogu P3247 思路 将所有边按$a$从小到大排序,然后枚举所有边,如果当前边加入可以让$b$的最大值更小或者让本来不连通的东西联通就加入,如果$1$和$n$联通了就更新一下答案 代码

[WC 2006] 水管局长

Luogu P4172 思路 删边不好做,所以可以考虑倒着来,现建出最后剩的边的最小生成森林,再把删边变成加边,倒着完成修改和询问 每次加边的时候,找到两点间路径上的边权最大的边,删掉,再连上现有的边 […]

[bzoj 3779] 重组病毒

bzoj 3779 思路 搞一个LCT维护联通块,把颜色相同的放在一个联通块里 搞一个线段树,以dfs序维护与根之间的联通块的数量 换根之后,线段树上的操作最多也只会分成两块,随便维护一下就可以了 代 […]