用栈思考稍显困难，不难发现我们可以建出一棵树出来，相当于对树进行二染色，对从根到任何点的路径上颜色数有要求，然后求愤怒值总和。
考虑一个简单的 DP，我们设 \(f_{u,p,x}\) 表示考虑点 \(u\) 内的子树，点 \(u\) 到根的路径上有 \(p\) 个 R，子树内一共有 \(x\) 个 R，每次合并。在根处稍微特殊处理就可以得到答案。这是 \(O(k^3)\)。
接下来我们有若干个优化方向：
- 放弃统计方案数，改成统计 \(\sum x^3,\sum x^2,\sum x\)。
- 坚持统计方案数，考虑优化 DP 的状态。（容斥？类似期望？）
- 考虑证明上面的 DP 复杂度是对的（显然是错的）。
然而我一个都不会。
我们考虑单纯记 DP 方案数太傻了，肯定要记答案。答案可以表示成从整棵树当中任选一个 R 和两个 B 的方案数，这个可以记 \(dp_{u,p,0/1,0/1,0/1}\) 来转移。复杂度 \(O(k^2)\)。
这个思路跟 ARC163 D 有点像。
标签：方案,UNR,sum,系统,考虑,提问,复杂度,DP From： https://www.cnblogs.com/PYD1/p/17551223.html