传递性_杂项 | JueFanBlogs

T3

一棵树，从一号点出发，点有点权，边有边权，经过一条边会将血量扣除这条边的边权，首次到达一个点血量增加这个点的点权。

任何时刻血量不能为负，问从 $1$ 出发回到 $1$ 至少要多少初始血量。

$n\le 10^5$ 。

这个题的关键部分是 $dp$ 柿子不写错以及顺序的推导。

首先简单设状态： $f_x$ 表示进 $x$ 这棵子树至少需要多少初始血量（不包括 $fa_x\to x$ 这条边）， $g_x$ 表示从进 $x$ 这棵子树到出来血量的变化量。

显然 $g_x$ 好求，它等于子树内 $-2\ \times$ 边权和 $+$ 点权和。

关键是 $f$ 的处理，我们最后的答案就是 $f_1$ 。

不难发现我们需要给子树安排一个顺序，若安排好了顺序，则转移式为：

$f_{x}\gets \max_{i=1}^{d_x} \left(f_{v_i}-\sum_{j=0}^{i-1}g_{v_j}\right)$

这个很简单，前面累计下来的血量可以作为一定的抵扣，而若抵扣不完，则我们初始就需要那么多血量用以抵扣，取一个 $\max$ 即可。

但这个转移柿子有一点点小问题，赛场上因为不管怎么都调不出样例心态崩了。

首先就是没有算上上来的边权。

$f_{x}\gets \max_{i=1}^{d_x} \left(f_{v_i}+w_{x\to v_i}-\sum_{j=0}^{i-1}\left(g_{v_j}-2w_{x\to v_j}\right)\right)$

其次，我们这里用 $f_{v_i}+w_{x\to v_i}$ 作为进入 $v_i$ 这棵子树的初始代价是片面的，你不仅应该保证走完整棵子树，你还应该保证最后走完上来这一步不会被憋死。

$f_{x}\gets \max_{i=1}^{d_x} \left(\max\left(f_{v_i}+w_{x\to v_i},g_{v_i}+2w_{x\to v_i}\right)-\sum_{j=0}^{i-1}\left(g_{v_j}-2w_{x\to v_j}\right)\right)$

这个时候柿子才算完整，我以后做 $dp$ 题的时候应该写一步检验一步是否正确，不能一步跨太大。

哦对了 $g_{v_0}$ 不能等于 $0$ ，应该等于 $a_x$ ，原因显然。

然后就是钦定顺序的问题了，一般这种题都是可以用 std::sort 来排的。

问题转化成有若干数对 $(f,g)$ ，你需要钦定顺序，使得 $\max\limits_{i=1}^{d_x}\left(f_i-\sum\limits_{j=0}^{i-1}g_j\right)$ 最小。

你观察到调换两个相邻的数并不会造成前后的取值变化，所以若调换两数使答案发生变化，则一定是这两个数之间的某个数使答案发生了变化，所以可以直接比较两数贡献。

设前方 $\sum g$ 是 $t$ ，则若 $x$ 应该排在前面：

$\max(f_x-t,f_{y}-t-g_x)< \max(f_y-t,f_x-t-g_y)\\\max(f_x,f_{y}-g_x)< \max(f_y,f_x-g_y)$

直接比较贡献：

1	bool cmp(S x,S y) {return max(x.f,y.f-x.g)<max(y.f,x.f-y.g);}

只能获得 $[90,95]$ 分，很难绷。

如果你是正序建边，那么你可以使用std::stable_sort()并采用以下 $hack$ ：

答案是 5，而有错误的程序输出 10。

通过调试，我们发现我们错误地安排了 $(10,-5),(0,0),(2,5)$ 这三个 $(f,g)$ 的顺序。

按上顺序排列的答案是 $10$ ，而 $(2,5),(0,0),(10,-5)$ 的答案是 $5$ .

我们尝试说明上述方法是错误的：

首先数学推导没问题，但问题出在了这个不等式上。

可以证明这个不等式的不等号具有传递性，这很好，但等号不具有传递性。

你发现 $(2,5)<(10,-5)$ 很明显是成立的，但 $(10,-5)=(0,0),(0,0)=(2,5)$ ，这错误地让 sort 觉得 $(10,-5)=(2,5)$ 。

所以在这种题中，我们需要给所有看似“相等”的对安排一个顺序，使得“相等”的对经过这个顺序排序后，那些能比较的对尽可能“撞”在一起。

而在本题，我们很明显发现 $g$ 的正负性应当作为第一关键字，所有 $g<0$ 的对不可能在 $g>0$ 前面。

事实上多了这个特判就可以了，但我想说两部分内容：

如何彻底拆掉这个 $\max$ 以证明不等号的传递性？

我们首先将 $\max/\min$ 变成且或符号，之后移项来看的更清楚（stO JCY_ Orz）：

$\begin{aligned}&(f_x,g_x)<(f_y,g_y)\\&\to \max(f_x,f_{y}-g_x)< \max(f_y,f_x-g_y)\\&\to\left( f_x< \max(f_y,f_x-g_y)\right)\bigwedge\left( f_y-g_x< \max(f_y,f_x-g_y)\right)\\&\to \left((f_x<f_y)\bigvee (f_x< f_x-g_y)\right)\bigwedge \left((f_y-g_x<f_y)\bigvee (f_y-g_x< f_x-g_y)\right)\\&\to\left((f_x<f_y)\bigvee (g_y<0)\right)\bigwedge \left((g_x>0)\bigvee (f_x+g_x>f_y+g_y)\right)\end{aligned}$

于是 $(f_x,g_x)<(f_y,g_y)$ 可以等价于 $\left((f_x<f_y)\bigvee (g_y<0)\right)\bigwedge \left((g_x>0)\bigvee (f_x+g_x>f_y+g_y)\right)$ 。

我们的排序关键字为 $\left\{\begin{aligned}&f_x+g_x>f_y+g_y,&&(g_x\le 0)\bigwedge (g_y<0)\\&f_x<f_y,&&(g_x>0)\bigwedge (g_y\ge 0)\\&g_x>g_y,&&\text{otherwise.}\end{aligned}\right.$

这覆盖了所有情况，且不重不漏，所以我们的不等号 $<,>$ 是有传递性的。

如何证明（或证伪）等号的传递性并解决等号不具有传递性的问题？

我们尝试证明等号有传递性（其实也就是证明 $\le,\ge$ 有传递性）。

我们试着套用刚刚的方法。

$\begin{aligned}&(f_x,g_x)\le(f_y,g_y)\\&\to \max(f_x,f_{y}-g_x)\le \max(f_y,f_x-g_y)\\&\to\left( f_x\le \max(f_y,f_x-g_y)\right)\bigwedge\left( f_y-g_x\le \max(f_y,f_x-g_y)\right)\\&\to \left((f_x\le f_y)\bigvee f_x\le (f_x-g_y)\right)\bigwedge \left((f_y-g_x\le f_y)\bigvee (f_y-g_x\le f_x-g_y)\right)\\&\to\left((f_x\le f_y)\bigvee (g_y\le 0)\right)\bigwedge \left((g_x\ge 0)\bigvee (f_x+g_x\ge f_y+g_y)\right)\end{aligned}$

$(f_x,g_x)\le(f_y,g_y)$ 可以等价于 $\left((f_x\le f_y)\bigvee (g_y\le 0)\right)\bigwedge \left((g_x\ge 0)\bigvee (f_x+g_x\ge f_y+g_y)\right)$ 。

排序关键字为 $\left\{\begin{aligned}&f_x+g_x\ge f_y+g_y,&&(g_x< 0)\bigwedge (g_y\le 0)\\&f_x\le f_y,&&(g_x\ge 0)\bigwedge (g_y> 0)\\&1,&&(g_x\ge 0)\bigwedge (g_y\le 0)\\&0,&&(g_x< 0)\bigwedge (g_y> 0)\end{aligned}\right.$

看上去也没什么问题，但是我们考虑反过来： $(f_y,g_y)\le(f_x,g_x)$ 。

排序关键字为 $\left\{\begin{aligned}&f_y+g_y\ge f_x+g_x,&&(g_y< 0)\bigwedge (g_x\le 0)\\&f_y\le f_x,&&(g_y\ge 0)\bigwedge (g_x> 0)\\&1,&&(g_y\ge 0)\bigwedge (g_x\le 0)\\&0,&&(g_y< 0)\bigwedge (g_x> 0)\end{aligned}\right.$

发现一个很难绷的问题，当 $(g_x=0)\bigvee (g_y=0)$ 时，我们判 $\le$ 的关键字冲突了。

所以我们其实用刚刚的方法证明了这个等号并不具有传递性。

assert了之后果然之前直接比较贡献过不去的点都 RE 了。

那如何通过定义sort中的“小于号”解决这个冲突呢？

考虑对 $(g_x=0)\bigvee (g_y=0)$ 使用某种关键字使其有正确的顺序。

原来的 $\max$ 肯定是不能用了，我们以上的推导都是充要的。

请循其本。

回到原题，你发现 $g_x>0$ 一定排在 $g_x=0$ 前面， $g_x=0$ 一定排在 $g_x<0$ 前面，这是显然不劣的。

所以我们对这部分的特判是按照 $g_x$ 为关键字降序排列。