zcmimi's blog

虚树是一种统计树上信息的技术

例题: LG 2495 [SDOI2011]消耗战

如果树的点数很少,可以直接树上dp

可以发现\sum k_i \le 5 \times 10^5

我们可以每次都把提供的k_i个点构造成一棵新树来跑树形dp

这样时间复杂度就刚刚好

虚树可以帮助我们构造出一棵包含这k_i个点的新树

虚树中包含了所有的关键点,也包含了所有关键点两两之间的LCA

虚树
comment评论
Search
search