显然只需要考虑叶子结点的连边情况，设一个结点 \(u\) 仅经过一条路径能到达的点的集合为 \(S_x\)，则条件等价于对于任意两个叶子结点 \(x, y\)，\(S_x\) 与 \(S_y\) 有交.
由树的性质，所有 \(S_x\) 的交集非空（否则存在环），于是交集为一个连通块，上点边容斥.
于是问题转化为两部分：求所有 \(S_x\) 都包含一个点 \(u\) 的方案数；求所有 \(S_x\) 都包含一条边的两个端点 \(u, fa_u\) 的方案数.
考虑容斥，第一部分记录 \(f_i\) 表示钦定 \(i\) 个叶子的 \(S_x\) 不包含 \(u\) 的方案数.
考虑将 \(u\) 的子树 \(v\) 并入 \(u\) 的转移方程.
\[f_{i+j}=f_i\binom{lef_v}{j}2^{(siz_u-i)(siz_v-j)} \]加入外子树时不必容斥，加完后统计一下答案即可，时间复杂度和树形背包一样，\(\mathcal{O}(n^2)\).
第二部分是第一部分的简单版，略过.
标签：结点,siz,容斥,叶子,P10064,公交线路,SNOI2024 From： https://www.cnblogs.com/0922-Blog/p/-/P10064_sol