专栏文章

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

sshaun2000
个人记录参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@minciqdf
此快照首次捕获于
2025/12/02 00:10
3 个月前
此快照最后确认于
2025/12/02 00:10
3 个月前
查看原文
下文即为 O(n3)O(n^3)
现在写 O(n2)O(n^2)
任意连边会使树变成一个个连通块
钦定一些边一定不被覆盖
令fi,jf_{i,j} 表示i在i所在子树的连通块大小为j 背包即可
记 hjh_j 为大小为j的连通块任意连边的方案数为 ∏i=1j/2（2∗i−1）\prod_{i=1}^{j/2}（2*i-1）
若该边被断：−fu,i∗fv,j∗hj→fu,i -f_{u,i}*f_{v,j}*h_j → f_{u,i}
不被断：fu,i∗fv,j→fu,i+jf_{u,i}*f{v,j} → f_{u,i+j}
答案为 ∑i=2nhi∗f1,i\sum_{i=2}^{n} h_i*f_{1,i}
下面假了，是并不需要容斥的 O(n3)O(n^3)
原因是可能是两颗子树间连边，须要枚举连了多少边
上面写做法
每条边至少被覆盖一次很烦，考虑容斥
钦定一些边不满足
令 fi,j,kf_{i,j,k} 表示i号点向上连j条边，其子树内有k条边不被覆盖
转移时每条边可选择向下连或向上连，背包即可。
答案为 ∑k=0n−1(−1)k∗f[1][0][k]\sum_{k=0}^{n-1}(-1)^{k}*f[1][0][k]
O(?)O(?) 不会算能优化到多少，反正不能过
考虑优化
显然k这一维可在转移的时候统计贡献，状态变为 fi,jf_{i,j} ，加入经典优化后复杂度为 O(n2)O(n^2)

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...