题解：Luogu P9260 [PA 2022] Miny

题意

给定一棵 \(n\) 个点的树，第 \(i\) 条边 \((a_i,b_i)\) 有边权 \(c_i\)，第 \(i\) 个点有一个爆炸半径 \(r_i\)。当一个点被引爆时，所有在该点爆炸半径范围内的点也会被引爆，这些新的被引爆的点也可能继续引爆其他点……对于每个点 \(i\)，求出该点被引爆后，最终会被引爆的点的数量。\(1\leq n\leq 10^5\)，\(0\leq r_i\leq 10^{18}\)，\(1\leq c_i\leq 10^{12}\)。

题解

rerererecallllll。

比较毒瘤。

考虑建图，对于每个点 \(i\)，向距离它不超过 \(r_i\) 的点 \(j\) 连一条有向边。对这个有向图缩点，考察一个强连通分量，显然引爆其中任何一个点都会让整个强连通分量中的点被引爆，于是每个点的答案就是在这个缩点后的 DAG 中可达的点数。

这样建图边数会爆炸，考虑优化建图。注意到建图条件是距离相关，因此考虑点分治优化建图。具体来说，设当前分治中心为 \(rt\)，考察所有 \(rt\) 子树内的点。设 \(dis_u\) 为 \(u\) 到 \(rt\) 的距离，那么对于处于 \(rt\) 不同的儿子子树内的两点 \(u,v\)，\(u\) 向 \(v\) 连边的条件为 \(dis_u+dis_v\leq r_u\)。而对于相同儿子子树内的两点，我们同样沿用这个条件即可，因为这相当于把限制放宽松了，并且我们向下递归到两点的 LCA 时，也会正确处理这两个点间的连边。

将 \(rt\) 子树内所有点按 \(dis\) 排序，枚举点 \(u\)，那么它连出去的点 \(v\) 需要满足 \(dis_v\leq r_u-dis_u\)，是一段前缀的点。我们可以使用前缀优化建图，建出 \(|sub_{rt}|\) 个虚点，从左到右第 \(i\) 个虚点，向第 \(i-1\) 个虚点连边，同时也要向排序后第 \(i\) 小的点连边。每次枚举点 \(u\) 时我们二分出分界点，向该分界点对应的虚点即可。这样我们就把图的点数和边数都压到了 \(\mathcal{O}(n\log{n})\) 级别，点分治建图的复杂度则是 \(\mathcal{O}(n\log^2{n})\) 的。

把图建出来缩点后，剩下的部分就是 DAG 可达性了。我们当然考虑建反图，在拓扑排序的过程中用 bitset 维护，但是这样子对于每个强连通分量我们都要开一个大小为 \(n\) 的 bitset，时空复杂度都是 \(\mathcal{O}\left(\dfrac{n^2\log{n}}{\omega}\right)\) 的，空间上无法承受。我们不妨分块，设块长为 \(B\)，每次取一个长度为 \(\mathcal{O}(B)\) 的编号区间 \([l,r]\) 出来，跑 DAG 可达性时只考虑这里面的点。这样空间复杂度降至 \(\mathcal{O}\left(\dfrac{nB\log{n}}{\omega}\right)\)，时间复杂度理论不变。

总体时间复杂度为 \(\mathcal{O}\left(n\log^2{n}+\dfrac{n^2\log{n}}{\omega}\right)\)。

这就能通过本题了吗？并不能。本题非常毒瘤，一些未经优化的地方常数是比较大的。接下来讲讲我是如何卡常的。

取不同的 \(B\)，时间复杂度只是理论不变，但实际运行中取稍大的 \(B\) 会对内存访问更友好，以我的实现取 \(B=1500\) 较为优秀。

可以发现我们不必显式跑拓扑排序。我们知道 Tarjan 跑出来的强连通分量编号是逆拓扑序，于是可以把 DAG 缩点后的反图中的每条边 \((u,v)\) 以 \(u\) 为第一关键字、\(v\) 为第二关键字排序，跑 DAG 可达性时只需依次访问每条边 \((u,v)\)，令 \(f_v\leftarrow f_v\cup f_u\) 即可。这样子没有了建图和遍历出边的开销，常数也优化了不少。

显然只有 \(1\sim n\) 所在的强连通分量是有用的，所以枚举强连通分量时的个数上界，应该设置成 \(1\sim n\) 所在的强连通分量的最大编号。

最后是最显著的优化。前缀优化建图时，\(\mathcal{O}(n\log{n})\) 个虚点带来的开销是巨大的，我们不妨只保留有用的那些。具体来说，对于一轮分治，我们把枚举点 \(u\) 时二分出的那些分界点对应的虚点视作关键点，对于相邻的关键点 \(p_i,p_{i+1}\)，把 \([p_i+1,p_{i+1}]\) 中的点全部缩成 \(p_{i+1}\) 这一个点。虽然这样子图的点数和边数的理论量级不变，但是实际数量会显著减少。

加上上面这些优化就跑的飞快了。

代码

这里放出主要的部分。

inline void dfs_rt(int x, int fx, int szrt) {int mxp = 0; sz[x] = 1;for (int i = T.head[x]; i; i = T.nxt[i]) {int y = T.to[i];if (!del[y] && y != fx) dfs_rt(y, x, szrt), sz[x] += sz[y], chk_max(mxp, sz[y]);}chk_max(mxp, szrt - sz[x]);if (mxp << 1 <= szrt) rt = x;
}
inline void dfs_dis(int x, int fx) {sz[x] = 1, pt[++szp] = {dis[x], x};for (int i = T.head[x]; i; i = T.nxt[i]) {int y = T.to[i]; ll z = T.w[i];if (!del[y] && y != fx) dis[y] = dis[x] + z, dfs_dis(y, x), sz[x] += sz[y];}
}
inline void dfs_solve(int x, int szrt) {if (szrt == 1) return;rt = 0, dfs_rt(x, 0, szrt), del[rt] = 1;szp = dis[rt] = 0, dfs_dis(rt, 0);sort(pt + 1, pt + szp + 1), fill(num + 1, num + szp + 1, 0);for (int i = 1; i <= szp; ++i) {int px = pt[i].second; ll dx = dis[px];int p = upper_bound(pt + 1, pt + szp + 1, pli{d[px] - dx, n + 1}) - pt - 1;if (p) {if (!num[p]) num[p] = ++tot;G.ins(px, num[p]);}}int lst = 0;for (int i = szp; ~i; --i) {if (i && !num[i]) continue;if (lst) {if (i) G.ins(num[lst], num[i]);for (int j = i + 1; j <= lst; ++j) G.ins(num[lst], pt[j].second);}lst = i;}for (int i = T.head[rt]; i; i = T.nxt[i]) {int y = T.to[i];if (!del[y]) dfs_solve(y, sz[y]);}
}
inline void tarjan(int x) {low[x] = dfn[x] = ++stmp, in_stk[stk[++top] = x] = 1;for (int i = G.head[x]; i; i = G.nxt[i]) {int y = G.to[i];if (!dfn[y]) tarjan(y), chk_min(low[x], low[y]);else if (in_stk[y]) chk_min(low[x], dfn[y]);}if (low[x] == dfn[x]) {++cscc; int p;do p = stk[top--], id[p] = cscc, in_stk[p] = 0; while (p != x);}
}
inline void solve(int l, int r) {for (int i = 1; i <= mxt; ++i) f[i].reset();for (int i = l; i <= r; ++i) f[id[i]][i - l] = 1;for (int i = 1; i <= sze; ++i) f[edges[i].second] |= f[edges[i].first];for (int i = 1; i <= n; ++i) ans[i] += f[id[i]].count();
}int main() {ios::sync_with_stdio(0), cin.tie(0);n = rd();for (int i = 1; i <= n; ++i) d[i] = rd();ll w; for (int i = 1, u, v; i < n; ++i) u = rd(), v = rd(), w = rd(), T.ins(u, v, w), T.ins(v, u, w);dfs_solve(1, tot = n);for (int i = 1; i <= tot; ++i) if (!dfn[i]) tarjan(i);for (int i = 1; i <= n; ++i) chk_max(mxt, id[i]);for (int x = 1; x <= tot; ++x) for (int i = G.head[x]; i; i = G.nxt[i]) {int y = G.to[i];if (id[x] != id[y]) edges[++sze] = {id[y], id[x]};}sort(edges + 1, edges + sze + 1);for (int i = 1; i <= n; i += B) solve(i, min(i + B - 1, n));for (int i = 1; i <= n; ++i) cout << ans[i] << ' ';return 0;
}