标签
树形 DP，线段树合并[NOI2020] 命运 - 洛谷P6773
这种计数题一般都和 DP 有关，再加上这个题不好容斥之类的，就直接尝试树形 DP 吧。
然后发现根本不会设计状态。这时我们要想想这个状态会和东西相关呢？
假设我们现在面对一个节点 \(x\) 以及它的子树，那么两个端点都在 \(x\) 子树内的点对就不用管了（已经处理完了），两个端点都不在 \(x\) 子树内的也不用考虑（以后再说），只需要考虑一端在 \(x\) 子树内，一端在外面（\(x\) 的祖先）的情况。
对于这些点对，只用考虑还没有 \(f(e) = 1\) 的那些点对 \((u, v)\)，而这些点对实际上只要管 \(u\) 的位置即可（反正 \(v \rightarrow x\) 上的 \(f(e) = 0\)），而且我们只需要这里面深度最大的 \(u\) 的深度即可。（因为对于深度最大的 \(u\) 都满足了，更浅的一定满足。）
于是我们就可以设计出一个 DP 状态了，令 \(dp_{x, i}(0 \le i < dep_i)\) 表示一端在 \(x\) 的子树内且还未满足的点对中 \(u\) 的最大深度为 \(i\) 的方案数（\(i = 0\) 则表示所有点对都满足了。）
考虑 \(x\) 与子树 \(y\) 合并时的转移，分 \(f((x, y)) = 0 / 1\) 讨论：
- \(f((x, y)) = 0\)，任意 \(dp_{y, j} \cdot dp_{x, i} \rightarrow dp_{x, i}\)。
- \(f((x, y)) = 1\)，设 \(dp_{y, j} \cdot dp_{x, k} \rightarrow dp_{x, i}\)，那么需要满足 \(j, k \le i\) 且 \(j = i 或 k = i\)。
所以 \(dp_{x, i} = dp_{x, i} \cdot \sum \limits_{j = 0}^{dep_y - 1} dp_{y, j} + dp_{x, i} \cdot \sum \limits_{j = 0}^{i} dp_{y, j} + dp_{y, i} \cdot \sum \limits_{j = 0}^{i - 1} dp_{x, j}\)。
初始化：\(dp_{x, mx_x} = 1\)，\(mx_x\) 表示 \(v = x\) 的点对 \((u, v)\) 中 \(\max \{dep_u\}\)。
使用前缀和优化搞到一个时空复杂度 \(O(n^2)\) 的做法，可以拿到 \(36pts\)。
一些小优化
注意到 \(mx_x\) 只有 \(O(m)\) 种，DP 可以进行离散化，做到时空均为 \(O(n \min(n, m))\)，拿到 \(64pts\)
听说还可以使用虚树骗到 \(72pts\)。但都和正解无关。
真正的优化
别问我怎么想出来的，因为我 ctj 了。
[PKUWC2018] Minimax - 洛谷P5298
正解是使用线段树合并优化这玩意。（可能是因为树，可以枚举到这个做法。）
令 \(s_{x, i} = \sum\limits_{j = 0}^i dp_{x, i}\)，那么 \(dp_{x, i} = dp_{x, i}(s_{y, i} + s_{y, dep_{y} - 1}) + dp_{y, i} \cdot s_{x, i - 1}\)。
线段树合并到最后有三种情况：\(x = 0, y = 0, l = r\)。
线段树维护 \(s_x\)，令 \(px\) 表示假设递归到最后为根乘的系数， \(py\) 同理。递归到左边，\(px, py\) 不变，递归到右边时 \(p_x +\!= sumy_l, p_y +\!= sumx_l\) 即可。
对于 \(x = 0 / y = 0\) 的情况，直接打个 \(\times py/px\) 的标记即可。值得注意的是 \(l = r\)，假设我们把 \(x\) 当成根，那么 \(sumx = sum_x(p_x + sumy) + sum_y \cdot py\)，是一个区间乘/加的 \(tag\)，于是线段树同时记录两个 \(tag\) 即可。（见代码）
时间复杂度：\(O(n \log n)\)
int Merge(int u, int v, ll pu, ll pv, int len) { // 合并 u, vif (!v) {update(u, pu % Mod, 0); return u;}if (!u) {update(v, pv % Mod, 0); return v;}if (len == 1) { // l = rupdate(u, (pu + tr[v].s) % Mod, pv % Mod * tr[v].s); return u; // tr[u].s = tr[u].s * (pu + tr[v].s) + tr[v].s * pu}Pushdown(u), Pushdown(v);tr[u].rs = Merge(tr[u].rs, tr[v].rs, pu + tr[tr[v].ls].s, pv + tr[tr[u].ls].s, len / 2);tr[u].ls = Merge(tr[u].ls, tr[v].ls, pu, pv, (len + 1) / 2);tr[u].s = tr[tr[u].ls].s + tr[tr[u].rs].s;(tr[u].s >= Mod) && (tr[u].s -= Mod);return u;
}
注意
有没有发现，我递归时先访问右边，再访问左边。因为如果倒过来，合并完左边后，tr[tr[u].ls].s 发生了变化，不是原来的了。
因为我们要求 \(i \le dep_{x} - 1\)，而合并完后，\(dp_{dep_x = dep_y - 1}\) 上会有值，需要清掉，因为这个状态不合法。
总结
这个题设计有两个难点：设计状态、优化转移。
设计状态可以从最简单的 \(dp_x\) 开始，思考状态会和什么有关，扩充状态，得到一个正确且很有前途的做法。
优化转移就可能需要多做一点题了。