P6805 [CEOI2020] 春季大扫除
思路：首先随意钦定一个不是叶子节点的节点为根节点。
然后考虑对于一个不是根节点的点 \(u\)，肯定需要至少一个叶子去与 \(u\) 子树之外的叶子节点配对。
考虑 \(u\) 到 \(fa_u\) 的这条边，首先至少有一个叶子节点穿过，然后设 \(p_u\) 表示 \(u\) 中的叶子节点个数：
[*]若 \(p_u\) 为偶，在一个叶子节点往外传后还剩奇数个，两两配对后还剩一个叶子节点，也需要往外传经过 \(u \to fa_u\) 的这条边。
[*]否则 \(p_u\) 为奇时，在一个叶子节点往外传后还剩偶数个，可以完美两两配对。
那么对于 \(u \to fa_u\) 的这条边，经过这条边的叶子节点个数为 \(1 + \)。
则总答案为：
\[\sum_{u \ne rt} 1 + = (n-1) + \sum_{u \ne rt} \]
考虑将 \(u \ne rt\) 给去掉，可以方便一些计算。
因为若 \(p_{rt}\) 不为偶数，就无法使得所有叶子节点配对，即无解，所以在有解的情况下 \( = 1\)，则需要将前面 \(-1\)。
则原式化为：
\\Big)\]
则每次在 \(u\) 处添加一个叶子节点，就相当于将 \(u\) 到根节点的 \(p_u \bmod 2\) 的值取反。
那么直接树剖维护即可，时间复杂度为 \(O(\Big(\sum D_i\Big) \log^2 n)\)。
要注意一下细节：在叶子节点下添加新节点，是没有贡献的（即不需要翻转），于是我们可以动态维护每个点的度数。
完整代码：
#include#define Add(x,y) (x+y>=mod)?(x+y-mod):(x+y)#define lowbit(x) x&(-x)#define pi pair#define pii pair#define iip pair#define ppii pair#define fi first#define se second#define full(l,r,x) for(auto it=l;it!=r;it++) (*it)=x#define Full(a) memset(a,0,sizeof(a))#define open(s1,s2) freopen(s1,"r",stdin),freopen(s2,"w",stdout);#define For(i,l,r) for(int i=l;i='0'&&c 感谢发布原创作品，程序园因你更精彩 感谢分享，学习下。 鼓励转贴优秀软件安全工具和文档！ 感谢分享 新版吗？好像是停更了吧。 喜欢鼓捣这些软件，现在用得少，谢谢分享！ 很好很强大我过来先占个楼 待编辑 前排留名，哈哈哈 喜欢鼓捣这些软件，现在用得少，谢谢分享！ 感谢发布原创作品，程序园因你更精彩 yyds。多谢分享 用心讨论，共获提升！ 这个有用。 懂技术并乐意极积无私分享的人越来越少。珍惜 很好很强大我过来先占个楼 待编辑 感谢分享，下载保存了，貌似很强大 鼓励转贴优秀软件安全工具和文档！ 收藏一下 不知道什么时候能用到 前排留名，哈哈哈
页:
[1]
2