ToB企服应用市场:ToB评测及商务社交产业平台

标题: P6805 [CEOI2020] 春季大扫除 [打印本页]

作者: 诗林 时间: 2024-8-16 10:31
标题: P6805 [CEOI2020] 春季大扫除
思绪：

首先随意钦定一个不是叶子节点的节点为根节点。
然后思量对于一个不是根节点的点 \(u\)，肯定需要至少一个叶子去与 \(u\) 子树之外的叶子节点配对。
思量 \(u\) 到 \(fa_u\) 的这条边，首先至少有一个叶子节点穿过，然后设 \(p_u\) 表现 \(u\) 中的叶子节点个数：

若 \(p_u\) 为偶，在一个叶子节点往外传后还剩奇数个，两两配对后还剩一个叶子节点，也需要往外传颠末 \(u \to fa_u\) 的这条边。
否则 \(p_u\) 为奇时，在一个叶子节点往外传后还剩偶数个，可以完美两两配对。

那么对于 \(u \to fa_u\) 的这条边，颠末这条边的叶子节点个数为 \(1 + [p_u \bmod 2=0]\)。
则总答案为：

\[\sum_{u \ne rt} 1 + [p_u \bmod 2 = 0] = (n-1) + \sum_{u \ne rt} [p_u \bmod 2 = 0]\]
思量将 \(u \ne rt\) 给去掉，可以方便一些计算。
因为若 \(p_{rt}\) 不为偶数，就无法使得所有叶子节点配对，即无解，所以在有解的情况下 \([p_{rt} \bmod 2 = 0] = 1\)，则需要将前面 \(-1\)。
则原式化为：

\[n -2 + \Big(\sum_u[p_u \bmod 2 = 0]\Big)\]
则每次在 \(u\) 处添加一个叶子节点，就相当于将 \(u\) 到根节点的 \(p_u \bmod 2\) 的值取反。
那么直接树剖维护即可，时间复杂度为 \(O(\Big(\sum D_i\Big) \log^2 n)\)。
要注意一下细节：在叶子节点下添加新节点，是没有贡献的（即不需要翻转），于是我们可以动态维护每个点的度数。
完整代码：

[code]#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

欢迎光临 ToB企服应用市场:ToB评测及商务社交产业平台 (https://dis.qidao123.com/)