传递性_杂项
JueFan 一只绝帆

T3

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

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

n≤105n\le 10^5。

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

首先简单设状态:fxf_x 表示进 xx 这棵子树至少需要多少初始血量(不包括 fax→xfa_x\to x 这条边),gxg_x 表示从进 xx 这棵子树到出来血量的变化量。

显然 gxg_x 好求,它等于子树内 −2 ×-2\ \times 边权和 ++ 点权和。

关键是 ff 的处理,我们最后的答案就是 f1f_1。

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

fx←max⁡i=1dx(fvi−∑j=0i−1gvj)f_{x}\gets \max_{i=1}^{d_x} \left(f_{v_i}-\sum_{j=0}^{i-1}g_{v_j}\right)

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

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

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

fx←max⁡i=1dx(fvi+wx→vi−∑j=0i−1(gvj−2wx→vj))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)

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

fx←max⁡i=1dx(max⁡(fvi+wx→vi,gvi+2wx→vi)−∑j=0i−1(gvj−2wx→vj))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)

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

哦对了 gv0g_{v_0} 不能等于 00,应该等于 axa_x,原因显然。

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

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

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

设前方 ∑g\sum g 是 tt,则若 xx 应该排在前面:

max⁡(fx−t,fy−t−gx)<max⁡(fy−t,fx−t−gy)max⁡(fx,fy−gx)<max⁡(fy,fx−gy)\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][90,95] 分,很难绷。

如果你是正序建边,那么你可以使用std::stable_sort()并采用以下 hackhack:

1
2
3
4
5
4
0 15 0 9
1 2 10
1 3 0
1 4 2

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

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

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

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

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

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

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

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

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

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

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

我们首先将 max⁡/min⁡\max/\min 变成且或符号,之后移项来看的更清楚(stO JCY_ Orz):

(fx,gx)<(fy,gy)→max⁡(fx,fy−gx)<max⁡(fy,fx−gy)→(fx<max⁡(fy,fx−gy))⋀(fy−gx<max⁡(fy,fx−gy))→((fx<fy)⋁(fx<fx−gy))⋀((fy−gx<fy)⋁(fy−gx<fx−gy))→((fx<fy)⋁(gy<0))⋀((gx>0)⋁(fx+gx>fy+gy))\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}

于是 (fx,gx)<(fy,gy)(f_x,g_x)<(f_y,g_y) 可以等价于 ((fx<fy)⋁(gy<0))⋀((gx>0)⋁(fx+gx>fy+gy))\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)。

我们的排序关键字为 {fx+gx>fy+gy,(gx≤0)⋀(gy<0)fx<fy,(gx>0)⋀(gy≥0)gx>gy,otherwise.\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 有传递性)。

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

(fx,gx)≤(fy,gy)→max⁡(fx,fy−gx)≤max⁡(fy,fx−gy)→(fx≤max⁡(fy,fx−gy))⋀(fy−gx≤max⁡(fy,fx−gy))→((fx≤fy)⋁fx≤(fx−gy))⋀((fy−gx≤fy)⋁(fy−gx≤fx−gy))→((fx≤fy)⋁(gy≤0))⋀((gx≥0)⋁(fx+gx≥fy+gy))\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}

(fx,gx)≤(fy,gy)(f_x,g_x)\le(f_y,g_y) 可以等价于 ((fx≤fy)⋁(gy≤0))⋀((gx≥0)⋁(fx+gx≥fy+gy))\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)。

排序关键字为 {fx+gx≥fy+gy,(gx<0)⋀(gy≤0)fx≤fy,(gx≥0)⋀(gy>0)1,(gx≥0)⋀(gy≤0)0,(gx<0)⋀(gy>0)\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.

看上去也没什么问题,但是我们考虑反过来:(fy,gy)≤(fx,gx)(f_y,g_y)\le(f_x,g_x)。

排序关键字为 {fy+gy≥fx+gx,(gy<0)⋀(gx≤0)fy≤fx,(gy≥0)⋀(gx>0)1,(gy≥0)⋀(gx≤0)0,(gy<0)⋀(gx>0)\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.

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

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

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

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

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

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

请循其本。

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

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

 评论
评论插件加载失败
正在加载评论插件
由 Hexo 驱动 & 主题 Keep
总字数 237.9k 访客数 访问量