https://www.becoder.com.cn/contest/5423
「HNOI2012」集合选数
感觉差不多会。
7/25 sh 杂题听课情况
-
NOI2018 冒泡排序【40】几乎不会
-
麦田里的守望者【40】打表找规律、最后 dp 不太理解
-
星空列车【40】完全不会
-
Were You Last：知道怎么做，但是不知道为什么是对的
-
AGC040E Prefix Suffix Addition：dp 不太理解
-
冒泡排序 完全没会
灯光展演
首先我们注意到一件事情：染的颜色数量并不是越多越好，最多为 \(c=\min\left(m,\left\lfloor\dfrac n2\right\rfloor\right)\)。
因为是树上的联通块，考虑将一个连通块的贡献分摊到边上。
接下来考虑先随便选一个根 \(u\)，对于她的每一条连边 \((u,v)\)，其有一次贡献等价于：存在一对点 \((x,y)\)，\(x\) 在 \(v\) 的子树内，\(y\) 在 \(u\) 的除 \(v\) 外的子树内。
显然，最优的情况下，每个子树内的颜色互不相同且都有匹配。
如果构造题答案存在上界，考虑构造一种方案正好取到这个上界。
Motivation1: 要使这样的点对尽量的多，感性的理解一下，应该要让每一个子树大小平均，因而想到用树的重心作为根节点。
Motivation2: 子树大小小于 \(c\) 且需要颜色不同，不妨直接按 dfs 序来染色。
可以证明这个方案最优，且取到答案上界。
证明如下：
设 \(v\) 是 \(u\) 子树大小最大的一个子儿子。
-
如果 \(siz_v\ge c\)：
由重心的性质，\(siz_v\le\left\lfloor\dfrac n2\right\rfloor\)，那么子树外的大小之和（包括根） \(\ge \left\lfloor\dfrac n2\right\rfloor\)，所以 \(v\) 子树内的所有的点（强于颜色）都能被匹配到。
同时，由于 \(v\) 子树已经包括了所有的颜色，那么对于每一个其她的子树中的颜色就一定能在 \(v\) 子树中找到匹配。
-
如果 \(siz_v <c\)：
由于我们是按照 dfs 序染的色，意一个点 dfn 序为 \(i\)，dfn 序为 \(i\pm c\)，的点如果存在，则其颜色一定与 \(i\) 相同，且不在 \(v\) 子树内（因为 \(v\) 子树还没到 \(c\) 那么大）。
同时由重心的性质，\(siz_v\le\left\lfloor\dfrac n2\right\rfloor\)，那么子树外的大小之和（包括根） \(\ge \left\lfloor\dfrac n2\right\rfloor\)，点 \(i\pm c\) 至少存在其一。
对于其她子树，其大小一定 \(\le siz_v< c\)，那么同理可证得。
标签：lfloor,Set,刘君实,子树内,题解,子树,right,siz,left From： https://www.cnblogs.com/CloudWings/p/18324122