Oddities

题目条件的充要条件是原图每个连通块点数都是偶数。 - 必要性：若为奇数，则总度数为奇数*奇数，还是奇数，但是每条边贡献两个度，总度数一定是偶数。矛盾。 - 充分性：对于一个偶数个点的连通块，我们一定能找到合法的边集，构造方式如下： > 随便抠出一颗生成树，随便定个根，从叶子开始向上重复这个流程：若该 ......

# CF603E Pastoral Oddities ## 题意 给定一张 $n$ 个点的无向图，初始没有边。 依次加入 $m$ 条带权的边，每次加入后询问是否存在一个边集，满足每个点的度数均为奇数。 若存在，则还需要最小化边集中的最大边权。 ## 题解 感觉自己找性质的能力还是太弱了。 首先有一个 ......