洛谷P3914 - 染色计数

 OI / 洛谷
被浏览

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

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

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

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

洛谷P3613 - 睡觉困难综合征

 OI / 洛谷
被浏览

首先我们要知道这道题的原型是「NOI2014」起床困难综合症。

总是有出题人喜欢把序列上用线段树解决的题目出到树上,让选手强行写个树链剖分或树分治或某种动态树数据结构。

序列问题转化为树上问题,很容易想到树链剖分,直接上板子。