一棵无根树如果以某个点为根后，所有子树大小都小于 $\lfloor\frac{n}{2}\rfloor$，则这样的点至多只有一个，且必定是重心。

如果以某个点为根后，所有子树大小都小于等于 $\lfloor\frac{n}{2}\rfloor$，则这样的点至多只有两个，也必定是重心，且如果有两个，则这两个点一定直接有边相连。

重心的最大子树大小不会大于 $\lfloor\frac{n}{2}\rfloor$。

虚树保留了所有关键点两两的 LCA，也可以看做是原树抠了一些点得到的，形态没有任何变化。

ABC 被我轻松开贺了，贺完学习一下。

范德蒙德卷积公式：$\displaystyle\sum_{i=0}^k {n \choose i}{m\choose k-i}={n+m\choose k}$，组合意义显然。

一个简单变式是 $\displaystyle\sum_{i=0}^m {n \choose i}{m\choose i}={n+m\choose m}$。

推论是 $\displaystyle\sum_{u\ge0} {x \choose u}{y\choose u+1}={x+y\choose y-1}$。

考虑直接 ${y\choose u+1}={y-1\choose u+1}+{y-1\choose u}$，于是变为 $\displaystyle\sum_{u\ge0} {x \choose u}{y-1\choose u+1}+\displaystyle\sum_{u\ge0} {x \choose u}{y-1\choose u}$。

对于前项，令 $v=u+1$，变为 $\displaystyle\sum_{v\ge1} {x \choose v-1}{y-1\choose v}$。

等价于 $\displaystyle\sum_{v\ge1} ({x+1\choose v}-{x\choose v}){y-1\choose v}$

所以原式等于 $(\displaystyle\sum_{v\ge0}{x+1\choose v}{y-1\choose v})-(\displaystyle\sum_{v\ge0}{x\choose v}{y-1\choose v})+(\displaystyle\sum_{u\ge0}{x\choose u}{y-1\choose u})=\displaystyle\sum_{v\ge0}{x+1\choose v}{y-1\choose v}$。

由变式得 $x+y\choose y-1$。

做这个的时候看到的。牛逼结论：$(a\times c)\bmod(b\times c)=(a\bmod b)\times c$，两者任何情况下（包括非模意义下）完全相等。

考虑 $a=q\times b + r$，其中 $0\le r< b$，那么 $a\times c=q\times b\times c+r\times c$，则有 $\text{LHS}=\text{RHS}$。

找树上两条不交路径等价于某个点的子树内外各选一条路径。