树上 LIS 的套路之一
因为是从 yyb 博客上抓的题，所以知道可以用线段树做。大概想了想，初步的想法就是用线段树来维护不同高度(?)的最长子序列长度。其实这样是可以的，输入高度时就先塞到每个点的动态开点线段树里，然后就可以把儿子的进行合并。合并儿子的时候，维护至少为 \(x\) 时能得到的最长子序列长度，所以我们可以用差分的方式来做一做（当然也可以做标记永久化的区间加）：从 \(w_u\) 的位置开始加上一个一，然后把上一次的 \(1\) 给删掉。
因为是从 yyb 博客上抓的题，所以知道可以用线段树做。大概想了想，初步的想法就是用线段树来维护不同高度(?)的最长子序列长度。其实这样是可以的，输入高度时就先塞到每个点的动态开点线段树里，然后就可以把儿子的进行合并。合并儿子的时候，维护至少为 \(x\) 时能得到的最长子序列长度，所以我们可以用差分的方式来做一做（当然也可以做标记永久化的区间加）：从 \(w_u\) 的位置开始加上一个一，然后把上一次的 \(1\) 给删掉。
刚开始想的时候以为是可以直接设置 \(dp[u][0/1]\) 来表示是否已经用掉了一次判断的机会，然而正解其实跟这个差不多，只是用了一种更模式化的做法。
首先对于 \(d = 1\)，答案就是 \(k^n\)。
对于 \(d = 2\)，其实发现可以用生成函数来直接乘：\( A(x) = \sum_{i = 0}^\infty \frac{1}{i!} x^i [2 | i] \)，那么答案就是 \( A^k(x)[x^n] \)。发现可以变通奇偶性，所以 \(A(x) = \frac{e^x + e^{-x}}{2}\)，然后试着二项式展开：
首先发现两端并不会影响，所以可以直接做分段的线性 DP。正常思考暴力，发现每次都需要枚举颜色，非常麻烦。但是我们可以发现一个特别好的性质：每一次区间的颜色都取决于这个区间的最后一个元素，因为意识到选其他颜色时，我们大可把这个区间的右端点进行调整，使得下一个区间不会更劣。