蚌埠住了。总结写了一坨没了。现在是速通版。废话没了。
差分约束
注意 queue 换 stack、SLF、判断出队次数等优化。
以及 SPFA 最短路跑出来答案最大，反之亦然。
换根 dp
可以根据定义去换。此外因为 \(f_v\) 是从 \(f_u\) 过来的，换根可以对 \(f_v\) 减去 \(f_u\) 的贡献，再进行操作。
Nearby Cows G
原题目链接：Link。
定义 \(f_{i, j}\) 表示以 \(i\) 为根节点距离为 \(j\) 的节点权值和。\(f_{i, 0} = c_i\)。
首先只考虑「下面」的部分（就是从 \(1\) 开始 dp 顺着的方向），那么就可以简单地 \(f_{u, j} = \sum_{v \in son_u} f_{v, j - 1}\)。
然后考虑「上面」的部分。因为是「上面」，是从 \(u\) 推到 \(v\)，和「下面」的 dp 顺序相反。这里直接在原 dp 数组上操作，完了就是上 + 下 = 总和。假设 \(f_u\) 已经处理好，那么我们可以发现，统计 \(f_v\) 的时候，是会有重复的（「下面」的部分）。
比如这里 \(f_{v, 2}\)，统计「上面」需要的是 \(f_{u, 1}\) 的「上面」，但是会多统计 \(f_{u, 1}\) 的「下面」，也就是 \(v\) 节点（本质是 \(f_{v, 0}\)）那么容斥一下。\(f_{v, j} = f_{u, j - 1} - f_{v, j - 2}\)。
具体可以这样：
for (int i = k; i >= 2; i--)
f[v][i] -= f[v][i - 2];
写到这里问题已经迎刃而解了。所以我之前为什么会看这个题半天啊？？？
Kamp
原题目链接：Link。
为什么和考试题一毛一样？？？周考是翻译赛是吧？？？
因为每一条边都有去有回，所以都会经过两遍。除了最后去的点不用回，于是可以减掉。然后答案就变成了 \(f_i = 2 \sum_{j = 1} ^ k dis_{i, p_j} - \max_{j = 1} ^ k dis_{i, p_j}\)。
这里求距离之和可以很简单地换根，跟求 size 差不多。然后后面不会了。。。果然还是不会这种减掉贡献的吗。。。先 to be continued。
网络流
蚌埠。做了这么多网络流的题，一夜回到解放前。
主要是一些 tricks。
-
拆点。比如点有权、删除点等操作，把点 \(x\) 拆成 \(x \to x'\)，然后对于原先的 \(u \to x \to v\) 变成 \(u \to x \to x' \to v\)，在边上控制啥的就行。
比如电视网络，有删除点，就拆点，然后边可以删可以不删，转化为最小割，拆出来的边容量是 \(1\)，对应过去是真正的边容量就是 \(+ \infty\)。
还有蜥蜴。要拆成入点和出点。中间的边代表跳跃，就可以通过边来限制了。
-
好像相应的还有拆边，原理类似。
-
最小割判定。这个真的很难蚌。我会感性理解为边可以选和不选，对应到与 \(S\) 或是 \(T\) 在一起。
典型的比如 OI wiki 中的例子。有 \(n\) 个物品和两个集合 \(A,B\)，如果一个物品没有放入 \(A\) 集合会花费 \(a_i\)，没有放入 \(B\) 集合会花费 \(b_i\)；还有若干个形如 \(u_i,v_i,w_i\) 限制条件，表示如果 \(u_i\) 和 \(v_i\) 同时不在一个集合会花费 \(w_i\)。每个物品必须且只能属于一个集合，求最小的代价。与 \(S\) 在一起的和与 \(T\) 在一起的就是两个不同的集合。割掉连 \(S\) 的就属于 \(T\) 集合，反之。然后两点之间的连边如果割掉了就代表不属于同一个集合（$S $ 连「左边的」，\(T\) 连「右边的」）。
那方格取数问题中，异色的连边为什么是 \(+ \infty\) 呢。因为这里是直接染出两个颜色，\(S\) 和 \(T\) 都表示不选，只是一个是黑色连一个是白色连。那么 \(S \to u \to v \to T\)（\(u, v\) 异色）是不能联通的，这样就保证会从 \(S\) 或者 \(T\) 割开。如果异色的连边不是 \(+ \infty\)，直接从中间割开美滋滋，这样就不对了。
为了加强我的自尊心（以及摸鱼），拿最近的题验证一下效果。
深海机器人问题
原题目链接：Link。
类似方格取数加强版。因为每条边只有第一次有价值，有一条容量为 \(1\)，费用为边的价值的边，然后剩下的都没用了，容量为 \(+ \infty\)，费用为 \(0\)。就这样，但是我之前不会。