题解 P4494 【[HAOI2018]反色游戏】
先考虑一个经典题，给定一棵树，有的点要求度数为奇数，有的为偶数，求一个合法方案。
我们发现每个叶子节点都会有一个父亲来调整其度数，所以对于每个叶子节点判断其到其父亲的边能否保留即可。
换而言之只要不存在奇数个度数要求为奇数的点那么总能构成出来一个合法解，且这个合法解固定。
考虑本题做法，我们随便搞出一棵生成树，那么只要不存在两个点度数要求为奇数，那么外部的边无论怎么选都可以视为上述子问题，所以总能够存在一个合法解。
所以此时的答案为
现在考虑删点之后怎么做。
容易发现删点之后可能会破坏连通性。对于可能的多个联通块，我们需要对于每个联通块计算答案。
对原图建立广义圆方树，那么删除一个点之后会有其连接的方点的边都会被破坏（因为此点是两者之间的割点）设点
那么只需要判断每个联通块内需要度数为奇数的点时候为奇数即可，这个可以直接在广义圆方树上统计，复杂度