洛谷P3914 - 染色计数

 题解 / 洛谷
被浏览

CSP-S 前要多做树上问题(主要是因为去年 NOIP D1T3、D2T1、D2T3 全是树上问题,然后爆炸了)

这题一看就是树形DP,状态也是一眼就能想到的。

令 $f_{i,j}$ 表示 $i$ 这个点染成 $j$ 的方案数,枚举 $son_i$ 的颜色来转移。

最后答案即为 $\sum_{i=1}^{m}f_{1,i}$ 。