方程式
这个搜索好骚啊。
首先直接枚举 20 个数来搞初始根。假设我们拿到了\(s\)个根，那么我们还剩下\(n – s\)个，肯定是重根。所以我们考虑直接搜索剩下的\(n – s\)到底是哪个重根。这个复杂度就是\(\Theta(s^{n – s})\)。至于我们怎么验证解的正确性，就是这道题的精髓了：考虑把这组解写成零点式：
\[ \prod_{i = 1}^n (x – a_i) = 0 \]
我们做一个小的多项式乘法展开这个积式，然后与原式的系数进行对比即可。
这个搜索好骚啊。
首先直接枚举 20 个数来搞初始根。假设我们拿到了\(s\)个根，那么我们还剩下\(n – s\)个，肯定是重根。所以我们考虑直接搜索剩下的\(n – s\)到底是哪个重根。这个复杂度就是\(\Theta(s^{n – s})\)。至于我们怎么验证解的正确性，就是这道题的精髓了：考虑把这组解写成零点式：
\[ \prod_{i = 1}^n (x – a_i) = 0 \]
我们做一个小的多项式乘法展开这个积式，然后与原式的系数进行对比即可。
翻译一下：
给你一棵带点权的树和一堆路径，问对于每一个点\(i\)有多少条路经满足\(w(s,i) = weight(i)\)。
听起来就挺毒瘤的，是吧。根据这一类树上问题的套路，考虑把所有路径拆成\((s \to LCA(s,t))\)和\((t \to LCA(s,t))\)，分开处理。我们先来处理\((s \to LCA(s, t))\)这一类问题：假设我们现在要知道路径\((s \to LCA(s, t))\)对点\(i\)的贡献，必须满足：
学习树上差分的前提是：
学习了这些之后，我们就可以开始学习树上差分了。树上差分的思想跟差分类似：都是在不得不求前缀和的情况下，将区间操作变为单点操作，降低复杂度。树上差分曾两次在 NOIp 系列比赛中出现过，所以学习树上差分很有必要（我怀疑是出题组不敢出树链剖分，但又要考察选手们对树上操作的熟悉程度，所以采用了这么个坑爹玩意）。我们先来学习一个基本的操作：点的链上区间加。