自动搬运

查看原文

来自洛谷，原作者为

	Soulist 再见了

搬运于2025-08-24 22:00:44，当前版本为作者最后更新于2020-06-19 21:38:02，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

先考虑一个经典题，给定一棵树，有的点要求度数为奇数，有的为偶数，求一个合法方案。

我们发现每个叶子节点都会有一个父亲来调整其度数，所以对于每个叶子节点判断其到其父亲的边能否保留即可。

换而言之只要不存在奇数个度数要求为奇数的点那么总能构成出来一个合法解，且这个合法解固定。

考虑本题做法，我们随便搞出一棵生成树，那么只要不存在两个点度数要求为奇数，那么外部的边无论怎么选都可以视为上述子问题，所以总能够存在一个合法解。

所以此时的答案为 $2^{m+1-n}$

现在考虑删点之后怎么做。

容易发现删点之后可能会破坏连通性。对于可能的多个联通块，我们需要对于每个联通块计算答案。

对原图建立广义圆方树，那么删除一个点之后会有其连接的方点的边都会被破坏（因为此点是两者之间的割点）设点 $i$ 的度数为 $x$，那么删除之后剩余的边数为 $m-x$，此时答案为 $2^{(m-x)+cnt-(n-1)}$，其中 $cnt$ 为联通块数量，即其在圆方树上的出度。

那么只需要判断每个联通块内需要度数为奇数的点时候为奇数即可，这个可以直接在广义圆方树上统计，复杂度 $\mathcal O(n+m)$