20240311
CF1929E *2300
题意: 一棵树, k 条简单路径, 想让这 k 条简单路径中都有至少一条边被染色, 问最少染色多少条边能满足这个条件, k 不大于 20
题解: k 很小, 考虑状压. 每一条边能影响的路径最多是 k 条, 可以用状态来表示每一条边影响的简单路径, 然后状态相同的边随便选一条就行, 效果是一样的, 那么会出现多少种不同的状态呢? 可以用虚树来考虑, 最多只会有 O(k) 种状态, 然后就是经典状压 dp 了.
标签:状态,路径,板刷,状压,2000,2500 From: https://www.cnblogs.com/Leonard7/p/18065773