[USACO22DEC] Barn Tree S 题解

Demeanor_Roy · 2022-12-24 17:27:03 · 题解

• 原题链接

• 赛时想法，有问题欢迎提出。

考虑将这棵树以 1 为根定形。为了方便表述，令 cow(x),now(x),sum(x) 分别为以 x 为根子树节点数，x 节点干草捆数，以 x 为根子树干草捆总数。

由于一定有解，所以最后每个节点干草捆平分，令其为 aim，即 aim=\frac{sum(1)}{n}。

自上而下考虑。首先一号节点没有父亲，此处的干草捆不够肯定就由儿子拿，多了肯定就往儿子拿。考虑它的一个儿子 x，有以下三种情况：

1. 若 sum(x)=cow(x)\times aim ：这种情况下 x 这棵子树自给自足，递归处理即可。

2. 若 sum(x)>cow(x)\times aim ：这时 x 这棵子树的干草捆数多了，于是在满足自己的需求下，多余部分全部堆到 x 给父亲即可。

3. 若 sum(x)<cow(x)\times aim ：此时父节点补给 x 节点足够的干草捆，使其能够自足。

考虑到时时刻刻干草捆数必须非负，所以我们得到一个这样的策略：先递归处理所有情况一，二的 x，将多余的干草捆堆到 x 结点处给父亲，然后从父亲向所有情况三的 x 补干草捆，再递归处理。

于是自上而下，对每个节点的儿子分情况讨论，时时刻刻维护上面三个数组可。

此时还有一个问题是该方案的最优性，这可以通过对每一条边考虑来证明，读者自证不难。

代码