AT_arc101_c [ARC101E] Ribbons on Tree(学习笔记)

shaun2000 · 2025-11-07 15:48:07 · 个人记录

下文即为 O(n^3)

现在写 O(n^2)

任意连边会使树变成一个个连通块

钦定一些边一定不被覆盖

令 f_{i,j} 表示i在i所在子树的连通块大小为j 背包即可

记 h_j 为大小为j的连通块任意连边的方案数为 \prod_{i=1}^{j/2}（2*i-1）

若该边被断： -f_{u,i}*f_{v,j}*h_j → f_{u,i}

不被断： f_{u,i}*f{v,j} → f_{u,i+j}

答案为 \sum_{i=2}^{n} h_i*f_{1,i}

下面假了，是并不需要容斥的 O(n^3)

原因是可能是两颗子树间连边，须要枚举连了多少边

上面写做法

每条边至少被覆盖一次很烦，考虑容斥

钦定一些边不满足

令 f_{i,j,k} 表示i号点向上连j条边，其子树内有k条边不被覆盖

转移时每条边可选择向下连或向上连，背包即可。

答案为 \sum_{k=0}^{n-1}(-1)^{k}*f[1][0][k]