CF2189F 关于选择带权重心不劣的证明

· · 题解

显然我不想做这题，但是看到讨论区有人问关于这个贪心不劣的证明，所以这里证一下。（为什么别的题解不会证明的东西总是直接写个显然或者注意到，或者直接略过不提，明明根本不显然，至少标注一下不会证啊）

下文不考虑 \sum\limits_{i=1}^n a_i=0 的情况。（这种情况太显然了）

首先容易发现只对同一个点进行操作不劣（也就是一定有至少一种只操作一个点的方案代价最小），这很好证明，假设不只对一个点进行操作，考虑最后一次操作为 w，最后一次非 w 的操作为 u，则操作序列的一个后缀必为 u,w,\cdots,w，然后令 v 为以 w 为根时 u 的父亲，则将 u 变为 v 一定不劣，于是用调整法不停将 u 变为以 w 为根时 u 的父节点，直到 u=w 为止。

于是一定有至少一个最优操作序列为对点 u 进行 k 次操作（k \in \mathbb{N}）。下面为了方便，记 f_{u,v} 为以 u 为根时 v 的父节点，g_{u,v} 为以 u 为根时 v 的子树的点权之和（点权就是该点的坚果个数），h_{u,k} 为对点 u 进行 k 次操作后点权不为 0 的点个数，s_{u,v} 为以 u 为根时 v 的子树，c_{u,k,v} 为对点 u 进行 k 次操作后点 v 的权值，S=\sum\limits_{i=1}^n a_i。

设某个权值不为 0 或度数 \ge 3 的带权重心为 G（若不满足此条件我不确定是否正确），则 \forall i \neq G, g_{G,i} \le \frac S2。

考虑固定操作次数 k(\in \mathbb{N})，此时只要满足 h_{u,k} \le h_{v,k} 就一定有 pk+qh_{u,k} \le pk+qh_{v,k}，也就是说只要 h_{u,k} \le h_{v,k}，则将 k 次对 u 的操作改为 k 次对 v 的操作一定不劣。

仍然使用调整法。我们来证明 \forall u \neq G,h_{u,k} \le h_{f_{u,G},k}。

设这棵树为 T，T' 为将 T 中度数 \le 2 且权值为 0 的点删去（若度数为 2 则将该点两边的点连边）后得到的树，f'_{u,v} 为在 T' 中以 u 为根时 v 的父节点。

记 v=f'_{G,u}。我们不停进行以下调整直到 u'=G。

因为 G \in s_{u,v}，所以 g_{u,v}=S-g_{v,u}=S-g_{G,u} \ge S-\frac S2=\frac S2。

使用反证法。假设 h_{u,k} \red\lt h_{v,k}。

由于 \forall i \neq u \land i \neq v,c_{u,k,i}=c_{v,k,i} 并且 h_{u,k}=\sum\limits_{i=1}^n [c_{u,k,i} \neq 0],h_{v,k}=\sum\limits_{i=1}^n [c_{v,k,i} \neq 0]，于是 h_{u,k}-h_{v,k}=[c_{u,k,u} \neq 0]+[c_{u,k,v} \neq 0]-[c_{v,k,u} \neq 0]-[c_{v,k,v} \neq 0]。而由于 S=\sum\limits_{i=1}^n a_i \neq 0，于是 c_{u,k,u},c_{v,k,v} \neq 0，所以 0 \gt h_{u,k}-h_{v,k}=[c_{u,k,v} \neq 0]-[c_{v,k,u} \neq 0]，得到 c_{u,k,v}=0, c_{v,k,u} \neq 0。

由于对 u 进行一次操作时 g_{u,v} 至多减少 1，而进行 k 次操作后 c_{u,k,v}=0 意味着 g_{u,v} 在进行 k 次操作后变为 0，也就是 k \ge g_{u,v} \ge \frac S2。

考虑对 v 进行 k 次操作。对于与 v 相邻的节点 w，我们有：

  1. 若 w \notin \mathrm{path}_{u,v}，则 k 次操作后 g'_{v,w}=\max(0,g_{v,w}-k)，而 k \ge g_{u,v} \ge g_{v,w}，于是 g'_{v,w}=0。
  2. 若 w \in \mathrm{path}_{u,v}，则 k 次操作后 g'_{v,w}=\max(0,g_{v,w}-k)，而 k \ge \frac S2 \ge g_{v,w}，于是 g'_{v,w}=0。

也就是说对 v 进行 k 次操作后仅有 v 的点权不为 0，于是 h_{v,k}=1，但是 h_{u,k} \ge 1，于是 h_{u,k} \ge h_{v,k}，与假设矛盾。

故 h_{u,k} \ge h_{v,k}，将对 u 进行 k 次操作调整为对 v 进行 k 次操作不劣。

不停调整直到 u'=G，于是 h_{u,k} \ge h_{u',k}=h_{G,k}，也就是说操作次数相同的情况下只对 G 进行操作一定可以使代价最小。

于是如果最优的操作序列为 k 个 u，则 k 个 G 也必为最优的操作序列。

结合以上两部分调整，命题得证。

本证明我做出来共耗时 20\rm{min}，但是打出来花了将近 1h 时间/kk