题解：P11468 有向树

No_commander · 2024-12-23 21:27:49 · 题解

记 f_i 表示 i 能到的节点数，g_i 表示以点 i 开始的简单路径的长度之和，初始化 f_i = 1 之后拓扑排序。

设一条边 v \to u，假设当前队头为 u，显然有：

因为 u 能到的点中每个点都会为 v 开始的简单路径的长度多贡献 1，所以有：

答案即为 \sum _ {i = 1} ^ n g_i。