摘要：
A - 小 N 的独立集 洛谷 - P8352 简单树形 \(dp\)，考虑设 \(f_{u,i,j}\) 表示以 \(u\) 为根的子树不选 \(u\) 最大权独立集为权值和为 \(i\)，可选可不选 \(u\) 最大权独立集为权值和为 \(i+j\)。转移是简单的。 但是，本题卡常，转移前判断一 阅读全文
posted @ 2026-01-09 21:31
Link-Cut_Trees
阅读(10)
评论(0)
推荐(0)
摘要：
A - DYN-Dynamite 洛谷 - P3523 神秘题，没场切。 题解 B - 高速公路现代化 Highway modernization 洛谷 - P3596 枚举割边，最小值的割边一定在直径上，计算出两颗树的直径，然后就可以随便做了。 考虑求分裂后的两棵树的直径。可以先从原树直径的两个端 阅读全文
posted @ 2026-01-09 21:20
Link-Cut_Trees
阅读(6)
评论(0)
推荐(0)
摘要：
首先二分，问题转换成每个被选中点可以标记距离祂 \(mid\) 以内的点，求最少需要选几个点。 考虑从深到浅贪心，对于每一个关键点，如果祂现在没被标记，最优的方案为选祂的 \(mid\) 级祖先，然后标记祂的 \(mid\) 级祖先的 \(mid\) 级邻域。标记直接暴力跑，记录一下每个点被标记时最 阅读全文
posted @ 2026-01-09 21:10
Link-Cut_Trees
阅读(31)
评论(0)
推荐(0)
浙公网安备 33010602011771号