[USACO18JAN] Cow at Large P

题解都说了，当统计$u$为根节点的时候，答案就是满足以下条件的$i$的数量：$d_i\ge g_i$且$d_{f{a}_i}<g_{f{a}_i}$，设这个数量为$ans$。以下严格证明

首先对于满足这个条件的$i$，其子树的叶子节点显然最多只有一个有农夫（否则就放多了）

我们考虑任意一个叶子节点$p$，有$d_p\ge g_p=0$，但是对于$u$又有$d_u=0<g_u$；于是我们猜想，从$p$到$u$的路径上，会有一个临界点，从$p$到这个临界点的点都有$d\ge g$，在这个临界点到$u$都有$d<g$

证：从$p$出发向$u$走，每一步$d$都会减少一，而$g$要么减少一（当前点到离当前点最远的叶子节点要先走到父亲节点再走到叶子节点，注意中途不会经过当前点）要么增加一（离当前点最远的叶子节点在当前点的子树中，并要满足某种限制条件）要么不变（离当前点最远的叶子节点在当前点的子树中，并且不满足某种限制条件，可以想一下这个限制条件是什么）。所以当第一次$d<g$后，之后$g$的减少程度一定不会超过$d$的减少程度，也就是说恒有$d<g$

有了上述性质我们就可以发现，对于任意一个叶子节点，其到根的路径上有且仅有一个点满足最开始给的不等式，所以对于任意一个叶子节点，我们都可以唯一地指定给一个满足最开始不等式的一个点，而满足最开始不等式的点所管辖的叶子节点集合一定不是空集，也就是说满足最开始不等式的点构成了叶子节点集合的一个划分；而且由上述证明过程可知，设$i$是满足最开始不等式的点，则离其最近的叶子节点一定在其所管辖的集合中，也就是其子树中（否则的话，$i$走到其父亲，$d$和$g$都会减一，仍有$d\ge g$，与最开始的不等式矛盾）

然后我们就可以知道，我们对于每个满足最开始不等式的点，选出离其最近的叶子节点放置农夫，这样就可以在$ans$个农夫中抓住bessie。而如果答案比$ans$小，那么由于鸽巢原理，肯定有一个满足最开始不等式的$i$，其叶子节点一个都没有放农夫，于是Bessie就可以往$i$走，在其走到$i$的时候，一定不会有农夫抓住他，然后她任选一个叶子节点就可以桃之夭夭了