填树
WeLikeStudying · · 题解
- 对自身的问题有了新的体会。
- 我应该做纯粹的学习者，不要总想着他人具有的优势，应该真诚地热爱，享受学习。
- 感谢大佬的指导，祝愿其信息学之路光芒璀璨。
题意
- 题目链接。
- 给你一棵树，每个点要么权值为
0 ，要么权值是[l_u,r_u] 之间的正整数，你可以选择上面的任意一条链使得它的权值不为0 。 - 求所有可能的，满足内部非
0 权值极差不超过k 的树的方案数和权值和。
暴力
- 嗯……先想简单的暴力……然后发现只有枚举的暴力，瞬间意识到了事情的严重性。
- 我们尝试枚举非
0 的节点的最小值，然后对应有一个较大值的上限，但存在一个问题：我们需要让至少一个非0 节点取到最小值。 - 尝试容斥，我们可以快速地解决求非
0 点权在[l,r] 之间的方案数（此时每个节点能取的范围就是[l_u,r_u] 与[l,r] 的交），所以我们用[l,r] 的方案数减去[l+1,r] 的方案数，就可以得到取到最小值的情况，然后设值域为w ，我们（如果不换根采用最朴素的树上动态规划）得到了O(n^2w) 的优秀（？）复杂度，代码，容易将这个相当暴力的算法优化成O(nw) ，代码。 - 你当时会觉得这很有前途吗，反正我当时并不觉得，但是实在没有其它东西可以推了啊，硬着头皮想下去吧。
分析
- 嗯……根据数据范围猜测复杂度是个好习惯，我们合理猜测最后的复杂度是
O(n^3) 或者O(n^4) 。 - 接下来怎么做呢？我们先把问题进行一些简化与归纳。
- 我们计算的是这样一些
[l,l+K] 的问题，需要树取到最小值l 而且非0 权值在这个区间内。 - 匀速滑动这个窗口，设
x 为区间的某个左右端点位置，我们发现当l_i=x,l_i+1=x,l_i+K=x 三者都不发生的时候，所有点的权值都在做均匀连续的变化，要么减一，要么不变，要么加一，更确切地，有O(n) 段这样连续的变化。 - 让我们考虑最简单的情况：一条链的第一问，将区间长度抽象成点，我们要求所有子区间的点权乘积和，将点权表示成一次函数的形式，我们猛然发现我们要求的就是一个
n 次多项式，可以插值求它的前缀和（别笑，我卡在这里了）。 - 那么对于一般的情况呢？我们发现它也是一个多项式，对于第一问，它的次数最高为
n+1 ，对于第二问，它的次数最高可能达到2n+1 ，但这最多只是常数有点大而已，我们只需要使用拉格朗日插值即可在O(n^3) 的复杂度内计算了。 - 我一开始想偏了，想要直接通过动态规划求出这个多项式，但是显然不好做，这个插值应该才是简洁的实现。
实现
- 你知道作者推到这一步忽然发现自己忘记拉格朗日插值的形式的痛苦吗！所以作者进行了手推拉格朗日插值的尝试：
- 构造
n 个n-1 次多项式，让第i 个多项式f_i(x) 当x=x_i 的时候为y_i ，x=x_j 且j\ne i 时为0 ，显然：f_i(x)=y_i\prod_{j\ne i}\frac{x-x_j}{x_i-x_j} - 所以最终我们就得到了多项式的表达式（这下应该不会忘记了）：
f(x)=\sum_{i}y_i\prod_{j\ne i}\frac{x-x_j}{x_i-x_j} - 最后：多项式的最高次数其实是
n+2 ，因为第一个问题总是不超过n 个式子的乘积和，是n 次式，第二个式子，单独考虑某个节点的出现次数，是二次式乘上不超过n-1 个式子的一次式，由于最终表示成前缀和的形式，所以次数要高一次，即n+2 次，可以利用它卡常。 - 代码实现。
- 最后，稍微提一下一种做法：其实可以不用拉格朗日插值的，虽然代码会稍微长一点，但是可以用树上背包来求出这个多项式具体的值然后用第二类斯特林数求其前缀和，它的复杂度也是
O(n^3) 的，但不论是树上高复杂度动态规划自带最多1/2 的常数，还是几乎卡不满的多项式次数，都会使得这个做法的常数比拉格朗日插值小很多，而且由于反着想并不容易，它才是考场上大多数人能够写出来的做法。