- 给定一张 $n$个点的无向图,初始没有边。
- 依次加入$m$条带权的边,每次加入后询问是否存在一个边集,满足每个点的度数均为奇数。
- 若存在,则还需要最小化边集中的最大边权。
- $n \le 10^5,m\leq 3\times 10^5 $
考虑静态图,显然首先满足联通块点数为偶数。
考虑当前图也必须联通块是偶数点,(因为去边之后分裂成联通也要满足偶数点)。
最小化边集中的最大边权,考虑维护最小生成树。
如果纯静态,我们可以从叶子节点类似递推选择尽量少的边。这样显然是可以有解.
但是这个时候我们仍然没有选出最优解。
瞎$JB$乱画发现,删掉的边都是分裂成$奇+奇$的,我们不断地尝试删除当前森林中边权最大的边,联通块就会分裂,如果产生分裂成$奇+奇$,表示这个边不能删,这里的操作用大根堆以及懒惰记号表示。
然后用$LCT$子树维护一下奇数的联通块有多少。
代码
1 |
|