Exchange-Argument
参考资料：2022 集训队论文《浅谈一类基于交换的贪心在信息学竞赛中的应用》
本文主要介绍树上形式。
一般形式
你需要为 $n$ 个元素安排一个排名，得到一个序列 $a$，最小化某函数 $F(a)$。
如果存在一个满足传递性和强完全性的关系 $\le$，满足 $a,b$ 均为元素， $ \forall a\le b,F(s_1+a+b+s_2)\le F(s_1+b+a+s_2)$，则按照 $\le$ 排序后的排名可以最小化 $F(a)$。
典例为 NOIP2012 国王游戏。
我们在这里略去证明，详见参考资料。
- 强完全性指 $\forall a,b, a\le b\bigvee b\le a$，显然满足强完全性一定满足自反性。
- 条件中 $\{s_1+a+b+s_2\}$ 为全集。
树上问题
例题
给定一棵树，需要为树的每个节点安排排名 $p_u$，父节点的排名需要低于子节点。每个点有一个价值 $c_i$，需要最小化 $\sum c_u\times p_u$。
分析与结论
唯一的变化是，对于原问题元素的比较 $\le$，拓展到了对于子序列的比较，即 $a,b$ 为原来元素的一个序列。
以下是一个重要结论
考虑一个元素 $v$，我们希望说明如果它的父亲 $u$， $u>v$，那么 $v$ 一定在 $u$ 之后立刻被选择，此时将 $v,u$ 合并，可以得到一个规模为 $n-1$ 的子问题。
考虑证明 $u$ 被选择后一定会选择 $v$，对于一个满足树的限制的排列 $p$，如果 $u,v$ 不相邻，那么由于 $v>u$，所以对于序列 $p_1,p_2\dots u,p_l,p_{l1} \dots p_r,v,\dots,p_n$，一定有 $u>p_{l,r} \bigvee p_{l,r}>v$，否则 $v<u$，如果为前者，那么交换 $u$ 和 $p_{l,r}$，后者同理，所以 $v$ 一定紧接着 $u$ 被选择。
我们可以用以下两种方式解决问题。
方式1
考虑最大的元素 $v$，显然可以合并它和它的父亲 $u$，变成一个新的规模更小的问题。
合并的过程可以用并查集维护连通块，注意区分并查集父亲和实际父亲。
使用 priority_queue 或者 set 可以实现加入删除和查询最小值，priority_queue 的方式是同时维护一个代表删除的 priority_queue，实际上 priority_queue 会比 set 快 $1$ 倍。
注意实现的时候，如果找到了根，那么根其实有可能不在 priority_queue 里面，可删除的 priority_queue 如果删除了不存在的元素是会出问题的，所以一定要特判掉。
复杂度 $O(n\log n)$
方式2
我们考虑对每个子树求其答案。
利用分析中的结论，不妨将一棵子树划分成一些必须连续选择的序列，作为树对排列顺序的要求，将这些连续的序列视为一个元素后，我们可以对序列按照正常方式排序得到最优解。
划分序列的过程是对于一棵子树 $u$，将它的所有儿子的序列拿来排序，尝试将 $u$ 与最小的序列合并得到新的序列，如果 $u$ 当前所在的序列较大，由于结论我们知道合并后一定能拿到最优解，否则停止合并，此时 $u$ 所在序列的权值最小，一定会被最先选择，其中 $u$ 又一定会被第一个选择。
容易发现合并的过程一定不会改变子树内的选择顺序。
合并时采用启发式合并，利用 set 或 priority_queue 维护当前子树序列，复杂度为 $O(n\log^2n)$，但优势在于可以求出所有子树的答案。
当然可以使用可并堆达到 $O(n\log n)$
注意到其实一遍 dfs 就可以解决问题，因为启发式合并复杂度保证的来源是合并一次的复杂度为 $O(\min(|u|,|v|))$，所以并不需要提前计算子树大小，直接合并即可，set 或 priority_queue 的 swap 操作是 $O(1)$ 的。
碎碎念
Exc-Arg 除了直接解决问题外，也可以用来简化问题，将选择元素并重排的问题变为排序后选择子序列的问题。
对于树上的情况，我还没有见到过相关的问题。