一些 trick(15) | 树上邻项交换

· · 个人记录

例题 1. ABC376G Treasure Hunting

给定一棵 N+1 个点的树，一开始在 0 号结点（根），接下来 N 次，每次可以访问一个父亲已经被访问过的结点。有一个关键结点，给定每个点是关键结点的概率 p_i，求在所有可能的策略中，第一次访问到关键结点的期望次数。

其实就是要找到一个拓扑序 $\{x_i\}$，最小化 $\sum i p_{x_i}$。考虑拓扑序实际上是类似一个归并的过程。考虑邻项交换，设一个连通块有 $c$ 个点，概率和为 $p$，则 $(c_1,p_1)$ 和 $(c_2,p_2)$ 谁前谁后的关系就是 $c_1p_2<c_2p_1$。这是一个严格弱序，因此可以邻项交换。用堆维护每个非根结点的连通块，每次找到最小的拼到它父亲后面即可。 例题 2. [AGC023F 01 on Tree](https://atcoder.jp/contests/agc023/tasks/agc023_f) 给定一棵 $N$ 个点的树，每个结点有 $0,1$ 的权值，求一个拓扑序，最小化最终序列中权值的逆序对个数。 $N\le 2\times10^5$。 和上题类似的分析可以立刻做出这题：设一个连通块中 $0,1$ 各有 $c_0,c_1$ 个，则 $(c_0,c_1)$ 和 $(d_0,d_1)$ 谁前谁后的关系就是 $c_1d_0<c_0d_1$，这是一个严格弱序，类似地做即可。 例题 3. [Problem H. Monster Hunter](https://acm.hdu.edu.cn/showproblem.php?pid=6326) 给定一棵 $N$ 个点的树，一开始在 $1$ 号结点（根），接下来 $N$ 次，每次可以访问一个父亲已经被访问过的结点。第一次访问一个结点 $X$ 的时候血量会先减少 $A_X$ 再增加 $B_X$，求为了保证每时每刻血量非负，最初血量的最小值。 $N\le 10^5,\sum N\le 10^6$。 其实题目就等价于给定一些序列 $[-A,B]$，最大化前缀和的最小值，相反数就是答案。而这种「前缀和最小值」型的括号序列状物有一个经典的比较。设和、最小前缀和分别为 $a,b$，则： - 若 $a_1\ge 0,a_2\ge 0$，则 $(a_1,b_1)$ 小于 $(a_2,b_2)$ 当且仅当 $b_1> b_2$。 - 若 $a_1\ge 0,a_2<0$，则 $(a_1,b_1)$ 小于 $(a_2,b_2)$。 - 若 $a_1<0,a_2\ge 0$，则 $(a_1,b_1)$ 大于 $(a_2,b_2)$。 - 若 $a_1<0,a_2<0$，则 $(a_1,b_1)$ 小于 $(a_2,b_2)$ 当且仅当 $a_1+b_2>a_2+b_1$。 与前面几题类似做即可。 例题 4. [P7011 [CERC2013] Escape](https://www.luogu.com.cn/problem/P7011) 题意不讲了。 总之在 $t$ 上挂个权值为 $+\infty$ 的点就是判断最小前缀和能否 $\ge0$，和上一题一样做即可。 已经加入 [一些 trick](https://www.luogu.com/article/o0yp5tx3)。