树形 DP 计数。 luogu8867 建造军营 对于图中一条非割边，看守与否都相同，因此可以用 Tarjan 算法求出边双再缩点，把非树边单独拿出来，讨论每一条树边。 然而貌似不是很好做，子树外是否建造会影响子树内。考虑设 $f_x$ 为军营只在以 $x$ 为根的子树中出现，且至少存在 $1$ 个军营的方案数。 转移时对于边 $(x,y)$，如果…