前言
题目链接：洛谷。
题意简述
给出一棵 \(n\) 个节点以 \(1\) 为根的有根树。对于第 \(2\leq i\leq n\) 个节点，其父亲 \(f_i\) 在 \([l_i,r_i]\) 中均匀随机。每个树的边有边权，初始为 \(0\)。
现在有 \(m\) 次操作，第 \(i\) 次操作表示将 \((u_i,v_i)\) 的路径上所有的边的权值统一加上 \(w_i\)。\(m\) 次操作结束后，对于所有 \(i=2\sim n\)，求 \((i,f_i)\) 边上权值的期望，对 \(998244353\) 取模。
\(1\leq l_i\leq r_i<i\)，\(n \leq 5 \times 10^3\)，\(m \leq 10^5\)。（原题 \(m \leq 5 \times 10^3\)。）
题目分析
这道题树的形态十分鬼畜，平常树上那一套都不管用了，于是变得无从下手。似乎能下手的只有随机等概率跳父亲这一操作。
修改之间独立，考虑某一次修改 \((u_i, v_i, w_i)\)，我们要对 \(u_i \sim v_i\) 上，除了 \(\operatorname{lca}(u_i, v_i)\) 处的答案都加上 \(w_i\) 与这种树的形态的概率之积，即期望。联想到跳 \(\operatorname{lca}\) 的过程，在 \(u = v\) 之前，每次选取深度较深的结点，往上等概率地跳一次父亲。
对于本题，深度不确定，但是我们只用保证不会跳过 \(\operatorname{lca}\) 即可。什么情况下会跳过呢？就是 \(u\) 跳到了可能成为 \(\operatorname{lca}\) 的点，下一步不能让它往上跳。显然，可能成为 \(\operatorname{lca}\) 的点是 \(u\) 和 \(v\) 当中较小的一个。
即，假设 \(u < v\)，\(ans_v \gets ans_v + w\)，\(v \gets f_v \in [l_v, r_v]\)，\(w \gets \cfrac{w}{r_v - l_v + 1}\)。
发现，一对 \((u, v)\) 会被多次访问，与其多次重复操作，不妨先将其记下来，然后一起往上更新。数据范围允许我们设 \(f_{u, v}\) 表示当前已经跳到了 \((u, v)\)，对 \(u \sim v\) 这条树链修改的期望。类比上面的转移，有：
\[\forall k \in [l_v, r_v], f_{u, k} \gets f_{u, k} + \cfrac{f_{u, v}}{r_v - l_v + 1} \]初始 \(f_{u_i, v_i} = w_i\)。我们要保证转移时刻有意义，即保证 \(u < v\)。上式若出现 \(k = u\) 的状态应舍弃；若出现 \(k < u\)，要把 \(f_{u, k}\) 变成 \(f_{k, u}\)。由于修改独立，我们在 \(m\) 次操作后一起转移。
至此，时间复杂度是 \(\Theta(n^3 + m)\)，考虑优化。
发现加上的数都是相同的，设 \(C = \cfrac{f_{u, v}}{r_v - l_v + 1}\)，对于 \(k < u\) 的情况和 \(k > u\) 的情况分别拎出来观察：
\[\forall k \in [l_v, \min \lbrace r_v, u - 1 \rbrace], f_{k, u} \gets f_{k, u} + C \]\[\forall k \in [\max \lbrace l_v, u + 1 \rbrace, r_v], f_{u, k} \gets f_{u, k} + C \]很明显的区间加操作，使用二维前缀和维护即可。
时间复杂度：\(\Theta(n ^ 2 + m)\)。
代码
#include <cstdio>
#include <iostream>
#include <cstring>
using namespace std;
const int N = 5020;
const int mod = 998244353;
inline int add(int a, int b) {
return a + b >= mod ? a + b - mod : a + b;
}
inline int sub(int a, int b) {
return a - b < 0 ? a - b + mod : a - b;
}
inline int mul(int a, int b) {
return 1ll * a * b % mod;
}
int Inv[N];
int n, m, L[N], R[N];
int f[N][N];
int ans[N];
inline void add(int x1, int y1, int x2, int y2, int v) {
if (x1 > x2 || y1 > y2) return;
f[x2][y2] = add(f[x2][y2], v);
f[x1 - 1][y1 - 1] = add(f[x1 - 1][y1 - 1], v);
f[x1 - 1][y2] = sub(f[x1 - 1][y2], v);
f[x2][y1 - 1] = sub(f[x2][y1 - 1], v);
}
signed main() {
scanf("%d", &n);
Inv[1] = 1;
for (int i = 2; i <= n; ++i)
Inv[i] = mul(mod - mod / i, Inv[mod % i]);
for (int i = 2; i <= n; ++i)
scanf("%d%d", &L[i], &R[i]);
scanf("%d", &m);
for (int _ = 1, u, v, w; _ <= m; ++_) {
scanf("%d%d%d", &u, &v, &w);
if (u == v) continue;
if (u > v) swap(u, v);
add(u, v, u, v, w);
}
for (int u = n; u >= 1; --u) {
for (int v = n; v >= u; --v) {
f[u][v] = add(f[u][v], f[u + 1][v]);
f[u][v] = add(f[u][v], f[u][v + 1]);
f[u][v] = sub(f[u][v], f[u + 1][v + 1]);
if (v > u) {
int val = mul(Inv[R[v] - L[v] + 1], f[u][v]);
add(u, max(u + 1, L[v]), u, R[v], val);
add(L[v], u, min(u - 1, R[v]), u, val);
ans[v] = add(ans[v], f[u][v]);
}
// for (int o = max(u + 1, L[v]); o <= R[v]; ++o) {
// f[u][o] = add(f[u][o], mul(Inv[R[v] - L[v] + 1], f[u][v]));
// }
// for (int o = L[v]; o <= min(u - 1, R[v]); ++o) {
// f[o][u] = add(f[o][u], mul(Inv[R[v] - L[v] + 1], f[u][v]));
// }
}
}
for (int i = 2; i <= n; ++i)
printf("%d ", ans[i]);
return 0;
}
后记 & 反思
遇到期望 / 概率的题目，要往 DP 的方向思考，而不是像无头苍蝇一样只会写一个爆搜。
遇到宏观情况很鬼畜的问题，往往微观上一次操作是可控的，那么着眼于微观，每次迈出一小步即可。
标签：x1,剖分,int,题解,x2,add,对树链,y1,y2 From： https://www.cnblogs.com/XuYueming/p/18365079