AGC010C Cleaning

发表于 更新于 分类于 ， ， 阅读次数：

题意：一棵树，第 个节点上有 个石头。

每次可以选择两个不同的叶节点（度数为 的节点），将两点间路径上的所有节点都取走一个石头，如果有某个点上没石头这个操作就不能进行。

判定能否取完所有石头。

，时限 。

先任找一个不是叶子的点为根。（若 则都是叶子，特判）

记 表示方案中穿过 的路径数目。对于叶节点，有 。

对于非叶节点，记 ，即从儿子延伸上来的路径条数。

这些路径可以选择两两合并，也可以继续延伸。可以列出方程 ：

根据这个方程，可以用一次 求出所有的 。

然后考虑如何判定，一个显然的条件是 。

此外， 各有上界。记 为子树内叶节点的权值和，则 ：

  • 这个套路和《Luogu4338 [ZJOI2018] 历史》一致。

当 点为根时，额外要求 。

若满足上述条件，不难归纳证明可以构造出合法方案。

复杂度 。