标签: DP

1 篇文章

AT4537 题解
AT4537:Independent Set Description 给定一棵含有 $n~(1 \leq n \leq 10^5)$ 个节点树,每一个节点可以染成黑色或白色,其中任意两个相邻的节点不能同时为黑色,求染色的方案数,结果对 $10^9+7$ 取模。 Solution 首先我们可以想到这是树形 DP,考虑如何转移。 统计总方案数需要用到一…