首页 > 代码库 > loj6172 Samjia和大树(树形DP+找规律)

loj6172 Samjia和大树(树形DP+找规律)

题目:

https://loj.ac/problem/6172

分析:

首先容易得出这样的dp式子

技术分享

然后发现后面那个Σ其实是两段区间,可以用总和减去中间一段区间表示,所以只要维护个前缀和就ok了

这样复杂度就是O(nm)的

但是题目中的m异常巨大,有1e9,好像不能用dp做

但我们可以找下规律,发现对于一个点,其所有dp值是前后对称的,而且中间有很长的一段都是相同的数字!

设某个点x深度为d,那么它受到最“偏”的影响是来自叶子节点的,状态值之间会差d*k

对于一颗树而言,深度最大值为n-1,所以状态值之间会差(n-1)k

也就是说对于每个点,只有左边一段(n-1)k、右边一段(n-1)k可能是不同的,中间辣么多数字全是相同的!

那么很显然,我们dp时候,原来数字要枚举1~m,现在只需要枚举1~(n-1)k就行了!这样使得dp数组里所有出现的数字没有遗漏

复杂度是O(n^2k)

loj6172 Samjia和大树(树形DP+找规律)