对于每个子树，显然下端点不在子树内的链不会对子树内部的覆盖情况产生影响，所以我们将所有下段点在子树内的链构的集合的一个能够完全覆盖该子树的子集称作一种合法方案；将一种合法方案的下段点最靠上的链称作最浅链。
我们要对于每颗子树的每种可能的最浅链取值，维护权值最小的合法方案。
儿子转移向父亲的过程中，需要加入答案最小的以下段点为儿子的链为最浅链的方案。此时贪心地选择子树内维护的所有合法方案中答案最小者，加上该链贡献即可。
多个儿子合并时，如果某条链被钦定为父亲答案中的最浅链，除了该链下段点所在的儿子子树，其余儿子子树中贪心选择所有合法方案中最小值即可。如果其余子树中的方案选择使得该链最终不是最浅链，这样构造出来的错误方案一定不优于钦定真实的最浅链为最浅链构造出来的方案，所以无关紧要。
于是我们需要这样一种数据结构：能够快速求出集合中最小值，快速给集合权值整体加 $k$，合并若干集合。因此使用可并堆。
至于在转移过程中不能完全覆盖子树而变得不合法的方案，可以 lazy 地进行弹出。即使用到某个集合最小值时再判断其合法性，不合法则弹出。
所有人按照 $l$ 从小到大排序，依次尝试匹配从左到右每一个凳子。如果当前考虑到第 $i$ 个人，在尝试匹配从左到右第 $j$ 个凳子，且不满足 $j\le l_i$，此时 $[1,i]$ 中至少有一个人需要选择满足 $j\ge r_i$ 的凳子 $j$，显然在这些人中选择 $r_i$ 最小者一定不劣。
左侧匹配完，再把所有第一步未匹配的点按照 $r_i$ 从大到小排序，然后类似地贪心匹配。
正确性大概来源于，匈牙利算法可以以任意顺序遍历每个尚未被匹配的点，以任意顺序遍历一个点的所有出边。
第二种做法，先用运用霍尔定理的推论，将题意转化为，选择多条线段，求线段条数加线段交的长度最大值。
枚举线段交的左端点 $l$，此时能够选取的线段的左端点一定 $\le l$。此时对于该点右侧的每个点 $r$，它作为线段交的右端点的答案是 $r-l+k$，其中 $k$ 为完全包含 $[l,r]$ 区间的线段数量。
于是给线段树上每个点 $i$ 赋初始权值 $i$，把线段按照左端点从小到大排序，依次枚举线段 $[l,r]$，在线段树上给 $[l,r]$ 区间加一，求 $[l,+\infty)$ 区间最大值即可。
首先，可以自由排序等价于可以任意交换满足 $a_i>a_{i+1}$ 的 $i,i+1$，于是等价于任意重排后保持原有顺序对不交换。
那么从前往后枚举 $t$ 中的每个字符，在保证不与已匹配的字符中小于它的冲突的基础上，贪心地匹配 $s$ 尽量靠前者即可。
对每个点分别求出到它最近的关键点 $f_u$，和它能到达的最近的关键点 $g_u$。
枚举每个点 $u$，如果 $f_u\not=g_u$，用 $k=\mathrm{dist}(f_u,u)+\mathrm{dist}(u,g_u)$ 更新答案。
枚举每条边 $(u,v,w)$，如果 $f_u\not=g_v$，用 $k=\mathrm{dist}(f_u,u)+w+\mathrm{dist}(v,g_v)$ 更新答案。
不难发现上述每个用以更新答案的值 $k$ 都对应着至少一条合法路径，所以我们只需要证明 $k$ 至少一次取到正确答案。
考察所有起点和终点均为关键点的路径中最短的一条 $p_0,p_1,p_2\cdots,p_{m}$，设其长度即原问题答案为 $t$，那么我们有以下结论：
否则不满足 $f$ 或 $g$ 的定义。
由此结论可以得出，我们的更新方法中 $k$ 取不到正确答案 $t$，当且仅当这条路径上的每个点 $u$ 都有 $f_u=g_u$，每条边 $(u,v,w)$ 都有 $f_u=g_v$。那么
$$\displaylines{f_{p_0}=g_{p_1}=f_{p_1}=g_{p_2}=\cdots=g_{p_{m-1}}=f_{p_m} }$$而我们又显然有 $f_{p_0}=p_0\not=p_m=f_{p_m}$。矛盾，所以我们的更新方法一定能够取到正确答案。
初始将所有点按照 $K_i$ 加入小根堆，此时堆顶一定选择法伤而非物伤。因为堆顶选择物伤势必导致至少一个其它怪物选择法伤，代价一定不少于堆顶直接进行法伤。
所以我们取出堆顶，更新其前驱节点，即以它为后继的节点。如果一个节点被它的所有后继都更新过，并且算下来物伤更优，那么将物伤作为它的花费加入堆。正确性类似，已经被弹出堆的点无法再更新堆内节点，所以堆顶能够贪心地确定它的策略。
我们称一星通关的关卡为 A 类，二星通关的关卡为 B 类。
将关卡序列按照 $b_i$ 从小到大排序，显然在最优解中所有 B 类关卡一定排在所有未通关关卡之前。
也即我们选择一个分界点，将分界点之前划为 B 类关卡，分界点之后划为 A 类关卡，接着选择一些 A 类关卡改为不通关，选择一些 B 类关卡划入 A 类关卡。一定存在合适的分界点使得上述方案能够得出最优解。
于是我们对于每个可能的分界点，先计算出目前的总代价，然后衡量将分界点左侧的 B 类关卡降格为 A 类和分界点右侧的 A 类关卡改为不通关能够获得的收益，那么此分界点能够构造出的最小代价为总代价减去所有选择中收益前 $2p+q-w$ 大之和，其中 $p,q$ 分别为分界点左右侧关卡数。
那么我们从左到右枚举分界点，用堆维护所有选择的代价即可。
从前往后依次考虑每个段，不难发现，某个段内要么不表演，要么在不与之前的表演冲突的前提下，尽可能多地表演，即不需要迁就后面的段而让当前的段少表演，否则将后面段的表演移到前面段来，一定不劣。
既然如此，我们只需要 DP 求前 $i$ 段中最多唱多少首歌，设为 $f_i$；在唱最多歌的基础上，最早什么时候结束，设为 $g_i$。
暴力转移是 $O(n^2)$ 的。
考虑满足 $g_j\le l_i-t$ 的转移 $j\to i$，$i$ 段的决策一定是从 $l_i$ 开始唱歌，所以在只从最后一个这样的 $j$ 更新，一定不劣。
而对于 $g_j>l_i-t$ 的所有转移 $j\to i$，每个 $j$ 在整个过程中最多进行一次这样的转移，所以可以暴力做。
给定一棵无根树，在树上选 $k$ 条路径，它们的并构成一个包含 $u$ 的连通块，要使连通块中包含的边的权值和最大。
一道纯粹的性质题。
首先，一棵树能够被 $k$ 条链覆盖，当且仅当它有不超过 $2k$ 个叶子。
这里必要性是显然的，至于充分性，构造任意一种所有叶子都被覆盖，每条边长度至少为 $1$ 的方案，如果树没有被完全覆盖，找出任意一条极长的没有一条边被覆盖的非空路径 $p$。显然 $p$ 的端点 $u,v$ 不为叶子，因为端点为叶子，意味着路径 $p$ 包含了叶子的唯一出边；而方案中所有叶子都被覆盖，意味着叶子的唯一连边也被覆盖，这与 $p$ 的要求矛盾。既然 $u,v$ 不为叶子，而 $p$ 极长，那么 $u,v$ 一定分别存在于两条覆盖路径 $s\to t,x\to y$ 上。此时我们调整方案，将这两条路径换成 $s\to x,t\to y$，原来被覆盖的所有边仍然被覆盖，而为被覆盖的路径 $p$ 被覆盖。因此我们不断进行这样的调整，这个过程一定会在有限步内结束。
其次，选择 $k$ 条链，构成的包含边权和最大的子图，一定是连通的。一个不连通的方案，通过上述调整方法可以使其变得连通，并且更优。也即我们只需要保证我们能够考虑到最优方案，并不需要注意我们是否考虑到了不连通的选链方案。
不难发现，包含边权和最大的连通块至少包含带权直径的端点中的一个，调整法易得。
鉴于正权树的带权直径的两个端点一定是叶子，问题形式变为，分别在以两个端点为根的树中，选择 $2k-1$ 个叶子，要求它们到根的路径的并形成的连通块包含 $u$，求连通块内边权和最大值。
抛开连通块包含 $u$ 的条件，进行一个简单的贪心——长链剖分（注意这里是划分边集，可能有出现在多个链中，而非像大多数树链剖分一样划分点集），然后选择最长的 $2k-1$ 条链构成该连通块。它的正确性也很显然，最优解必然可以表示为几个长链的并，否则一定存在某个长链，该方案只包含了这个长链的某个真子集，那么此时将这个长链并入该方案，不会使其产生新的叶子，却会使该方案的答案增加。每个长链恰含有一个叶子，也即我们能够选择最多 $2k-1$ 条长链。所以选择长度最长的 $2k-1$ 条长链一定不劣。
如果这样构造出来的方案不包含 $u$ 呢？我们需要做出一些调整。
第一种调整方法是只选长度最长的 $2k-2$ 条链，外加一条根到 $u$，再到 $u$ 子树内深度最大点的路径。
第二种调整方法是将 $u$ 的最近的在连通块内的祖先 $f$，不选 $f$ 以及它所在的长链中 $f$ 以下的部分，而是选择 $f$ 到 $u$，再到 $u$ 子树内深度最大点的路径。
首先将原题题意转化为，构造排列 $p$，要求在有根树上如果 $u$ 是 $v$ 的父亲，则 $p_u<p_v$。
最大化 $\sum p_iw_i$ 的值。
从极端情况入手，考察树上权值最小的非根点 $u$，不难发现它在排列上紧随其父亲 $f$ 之后（即 $p_u=p_f+1$）一定不劣。于是我们便可以将 $f$ 和 $u$ 作为一个连续段考察。具体来说是将两个权值放进一个节点中，新节点的儿子为 $u$ 的所有儿子和 $f$ 除了 $u$ 之外的儿子，新节点的父亲为 $f$ 的父亲。
那么我们不免想到，经过第一次合并后整个序列是否能够按照类似的方式继续贪心地合并呢？
我们考察一个平均权值最小的连续段 $u_1,u_2,\cdots,u_s$，证明它在排列上紧随其父亲之后一定不劣。
考虑一种它没有紧随其父亲之后的方案，假设它前面一个连续段为 $v_1,v_2,\cdots,v_r$，$v$ 前面排列里有 $p$ 个数，我们交换 $u,v$ 所带来的答案增量为
$$\displaylines{\begin{aligned} \Delta&=\left(\sum_{i=1}^s(p+i)u_i+\sum_{i=1}^r(p+i+s)v_i\right)-\left(\sum_{i=1}^r(p+i)v_i+\sum_{i=1}^s(p+i+r)u_i\right)\\ &=s\sum_{i=1}^rv_i-r\sum_{i=1}^su_i\\ &=rs\left(\frac{\sum_{i=1}^rv_i}r-\frac{\sum_{i=1}^su_i}s\right)\\ &\ge0 \end{aligned} }$$由此可得，如果 $u$ 前面不紧邻父亲，那么交换它与它前面的连续段之后一定不劣。
此时做法已经呼之欲出——用数据结构维护所有可合并连续段，每次找到平均权值最小的，将它和父亲合并，同时维护连续段内贡献。
这道题的方案限制是在树上做出的，所以我们不免会想到对子树考虑是否可以设计状态使其具有最优子结构，并且便于转移。
发现这些限制在儿子向父亲转移时具有极良好的性质：
那么下面贪心合并的方案是显然的：两个子树分别按照段内最大值（即该段贡献）从小到大排序，然后两个子树一一对应合并，分段较多的子树剩下的段不合并。
还需要证明最优子结构性，即在儿子子树的最优方案中被分到同一段的元素，父亲处被分到同一段一定不劣。
我们用某个方案中所有段的大小升序排序后得到的序列代表它。如果两个方案 $a,b$ 满足对于任意位置 $i$ 都有 $a_i\le b_i$，我们称方案 $a$“严格不劣于”$b$。不难发现这样的关系构成了偏序，我们证明同一个子树内所有方案构成的偏序集的极小值是唯一的。
叶子节点本身构成的子树只有一种方案，所以极小值唯一；两种极小值唯一的偏序集按照上述方法进行合并，如果 $x$ 严格不劣于 $a$，$y$ 严格不劣于 $b$，并且 $x\not=a$ 或 $y\not=b$，那么显然 $x,a$ 合并后严格不劣于 $y,b$，并且两者不相等。