题目大意

• 给定一棵 $n$ 个点的无根树，每条边有一堵墙，高度在 $[l_i,r_i]$ 等概率出现。
• 有 $m$ 个僵尸，第 $i$ 只僵尸初始出生在 $x_i$ 点，能力值为 $h_i$，表示可以走过墙的高度 $
• 称一个点是安全的，当且仅当它不能被任何一个僵尸走到。

• 求树上至少有一个点是安全的概率，对 $998244353$ 取模，有 $T$ 组数据。

  • $T\leqslant 5,1\leqslant n,m\leqslant 2000,1\leqslant x_i\leqslant n,1\leqslant l_i,r_i,h_i\leqslant 10^9$，保证 $r_i-l_i+1\neq 998244353$。
  • $\texttt{source:[Nowcoder2018 ACM多校第十场 I] Rikka with Zombies}$（https://ac.nowcoder.com/acm/contest/148/I）。

Read more...

考虑从左往右逐个加入数字，如果线索必须是从左往右怎么做？首先考虑状压已经出现过的线索，线索出现的位置可能重叠，那么我们考虑一条线索开始时的位置，此时若有别的线索还没结束，那么一定需要满足完成新的线索之时或之前能够完成旧的线索。

设 $f(S,i,j)$ 为已经出现了线索集合 $S$ ，当前最后一个开始的线索为 $i$ 且匹配到第 $j$ 位时最短的序列长度，预处理 $a(i,j,k)$ 表示匹配到第 $i$ 条线索的第 $j$ 位时能否换到第 $k$ 条线索进行匹配。

转移时往下再匹配，或者枚举一条新的满足条件的线索，这是一个边权只有 0 和 1 的最短路，时间复杂度 $O(n^2 \cdot 2^n)$。

如果只有从右往左的线索呢，从左往右的时候我们考虑线索开始的时刻，那么现在就考虑线索结束的时刻，结束的时候枚举下一条线索计算最多能够重叠多少，即记 $b(i,j)$ 为第 $i$ 条线索结束时接第 $j$ 条线索最多可以匹配到第 $j$ 条线索的第几位，状态和转移类似，时间复杂度 $O(n^2 \cdot 2^n)$。

接下来就是考虑如何把向左的和向右的结合在一起，设 $f(S,i,j,k,l)$ 为当前出现了集合 $S$ 中的线索，从左到右的第 $i$ 条线索匹配到第 $j$ 位，从右到左的第 $k$ 条线索匹配到第 $l$ 位的答案，特殊地当 $i$ 或 $k$ 等于 0 表示当前没有这个方向的线索正在匹配。转移的时候往一边扩展一位，或者枚举一个新的线索替换某一跟方向的线索，注意扩展一位的时候处理好另一个方向的变化，同样是边权为 0/1 的最短路。时间复杂度 $O(n^3 \cdot 2^n)$。

0513上午

1、子图

导出子图（Induced subgraph）

• $G=(V,E)$，$G$ 在 $v_1$ 上的导出子图 $G_1=(V_1,E_1),E_1=\{e\in E\mid u,v\in v_1\}$
• 相当于在图中去掉一些点。$n$ 阶导出子图有 $2^n$ 个。

生成子图（Spanning subgraph）

• $G=(V,E)$，$G_1$ 为 $G$ 生成子图是指 $V(G_1)=V(G),E(G_1)\subseteq E(G)$
• 相当于在图中去掉一些边。生成子图有 $2^{|E|}$ 个。

$\color{red}{\texttt{Note: }}$

• 导出子图和生成子图都不限定是否为简单图。
• 既是导出子图又是生成子图为原图。

2、Mantel 定理、托兰定理

Mantel's thm

• 如果图 $G=(V,E)$ 中没有三角形，则 $|E|\leq [\frac{n^2}4]$ 。
• 等号成立条件 $\Longleftrightarrow$ $G=K_{\lfloor \frac n2\rfloor\lceil \frac n2\rceil}$。

Turan's thm

• 若 $G$ 无 $K_k$ 子图，$G$ 的边数取最大值的图唯一，为$G=K_{x_1,x_2,...,x_{k-1}}$，其中$\sum_{i=1}^{k-1} x_i=n$，同时 $|x_i-x_j|\leq 1$。
• 形式化的，$G=K_{[\frac n{k-1}][\frac {n+1}{k-1}]...[\frac{n+k-2}{k-1}]}$，$\sum_{i=0}^{r-1} [\frac{x+i}r]=[x]$。

3、二分图

二分图（Bipartite Graph） 定义

• $G=(V,E),V=A\cup B$。
• $\forall u,v\in A,(u,v)\notin E$ 且 $\forall u,v\in B,(u,v)\notin E$。
• 则称 $G$ 为二分图。

二分图判定定理

• 一个图 $G$ 是二分图，当且仅当图 $G$ 无奇环。
• 命题①：$G$ 是二分图
• 命题②：$G$ 无奇环
• 命题③：$G$ 无奇数长的回路
• 通过 ①$\Rightarrow$②$\Rightarrow$③$\Rightarrow$① 可证得三个命题相互等价，在此略去。

4、完美匹配、Hall定理、Tutte定理

匹配（Matching）

• $G=(V,E)$，$E$ 的子集 $E_1$ 的顶点两两不重合。则 $E_1$ 为 $G$ 的匹配。

完美匹配（Perfect Matching,PM）

• 匹配 $E_1$ 的顶点覆盖 $V$，$G$有PM $\Rightarrow$ $|G|\equiv 0(\operatorname{mod} 2)$

二分图完美匹配

• $G$ 为二分图 $(x,y,E)$。
• $G$ 有 PM ，则 $|X|=|Y|$ 且 $X$ 到 $Y$ 有双射。
• $f$ 称为由 PM $E$ 诱导（induce） 的双射。
• 满足 $f(x_i)=y_i,(x_i,y_i)\in E(E_1=\{(x_i,y_i)\mid 1\leq i\leq |X|\})$。

Hall 定理

• 二分图有完美匹配的充要条件为：$\forall S\subseteq X，|N(S)|\geq |S|$（有匹配覆盖 $X$ 的所有顶点），$\forall S\subseteq Y,|N(S)|\geq |S|$（有匹配覆盖 $Y$ 的所有顶点）。

Tutte 定理

• 对于图 $G$ ，$G$ 有PM的充要条件为 $\forall S\subseteq V$ ，$G$ 在 $V-S$ 上的导出子图 $M$ 的有奇数个顶点的连通分支的个数 $\leq |S|$。

5、正则图的定义

正则图

• 一个图为 $k-\texttt{正则}$ 的，定义为 $\forall v\in V,d(v)=K$ 。

0513下午

1、欧拉图的定义

欧拉图 Euler Graph

• 存在一条回路，经过图 $G$ 的全部的边恰好一次。（欧拉回路）

2、一笔画的算法，欧拉图的充要条件

• 若一个图 $G$ 存在 $0$ 个或 $2$ 个奇点，则这个图可以一笔画。
• 欧拉图充要条件：$\forall v\in V,2\mid d(v)$。

3、哈密顿（Hamilton）图、哈密顿链的定义

哈密顿图

• 一个图 $G$ 为哈密顿图 $\Longleftrightarrow$ 存在一条回路包含图 $G$ 的全部顶点，这个回路被称为 Hamilton 圈。

哈密顿链

• 若一条链 $P$ 遍历了图 $G$ 的全部顶点，则称 $P$ 为哈密顿链。

4、Hamilton 性质、必要条件

必要条件

• 设 $S$ 为 $G$ 的一个顶点子集，若 $G$ 在 $V-S$ 上导出子图的连通分量个数大于 $|S|$ $(|S|+1)$ ，则 $G$ 无哈密顿图（链）。
• 二分图有哈密顿圈（链），必要条件为 $||X|-|Y||\leqslant 0$（$1$）。

5、哈密顿图（链）的一些充分条件：Ore条件、Dirac条件

Ore 条件

• 若 $G$ 为哈密顿图，设 $|G|=n$，则 $\forall v,d(v)\geqslant \frac{n}{2}$。

Dirac 条件

• 若 $G$ 为哈密顿图，设 $|G|=n$，则 $\forall u,v$，若 $(u,v)\notin E$ ，$d(u)+d(v)\geqslant n$。
• 若 $G$ 存在哈密顿链，则 $d(u)+d(v)\geqslant n-1$。

6、图的笛卡尔积的定义

• 集合的笛卡尔积： $A\times B=\{(a,b)\mid a\in A,b\in B\}$。
• 图的笛卡尔积： $G=(V,E)\space ,\space H=(U,F)$。
• 定义 $G\times H=(V\times U,E')$。$E'=\{(v_1,u)(v_2,u)\mid v_1,v_2\in E,u\in U\}\cup\{(v,u_1)(v,u_2)\mid u_1,u_2\in F,v\in V\}$。

0514上午

1、图的顶点染色

染色的定义

• 一般染色：$f:x\rightarrow \{1,2,3,\cdots,k\}$。其中，$1\cdots k$ 是颜色集合。（高联一般不考虑无穷染色）
• 图的顶点染色：$G=(V,E)$
  • 无限制的染色：$f:V\rightarrow \{1,2,3,\cdots,k\}$
  • 一般意义上的图染色：$f:V\rightarrow \{1,2,3,\cdots,k\}$，且对于 $\forall(a,b)\in E,a\neq b,f(a)\neq f(b)$

染色数的定义

• 最小使得染色映射 $f$ 存在的 $k$ 称为图 $G$ 的色数，记为 $\chi(G)$。（chromatic number）

$\color{red}{\texttt{Note: }}$

• $n$ 阶图一定可以用 $n$ 种颜色染色。随机图算色数较为困难。
• 答题方法：考试时将颜色标在图上，再证明不存在更少的色数。
• 常用结论：
• $\chi(K_n)=n$（ $n$ 阶完全图 ）
• $\chi (C_n)=\begin{cases} 2, &2\mid n \\ 3, &2\nmid n \end{cases}$（ $n$ 个点的环）
• $\chi (T)=2\ (n\geqslant 2)$ （ $n(n\geqslant 2)$个点的树）

2、色数的简单估计

估计色数上下界

下界

• 团数（clique number）：设团数 $\omega(G)$ 为 $G$ 中最大完全子图的阶数。

• 明显的下界：$\chi (G)\geqslant \omega(G)$。

• 最大独立集：一个图的最大独立集 $S\subseteq V$，是指点数最大的两两不连的顶点集合。

• 独立数（independence number）：设独立数 $\alpha(G)$ 为图 $G$ 的最大独立集顶点数。
• 另一个下界：$\chi(G)\geqslant \frac{n}{\alpha(G)}$。

上界

• 上界：$\chi(G)\leqslant 1+\Delta(G)$。

3、Brooks 定理简介

Brook's Thm

• 设 $G$ 为连通图且不是完全图或奇圈。则必有 $\chi(G)\leqslant \Delta(G)$。
• 前提的等价表述：$\Delta\geqslant 3$，且$\exists\ u,v\in V,(u,v)\notin E$。

4、色多项式（chromatic polynomial）

• 我们考虑一张一般的图 $G$ ，将它 $k$ 染色的方案数。
• 我们在图 $G$ 上任取一条边 $e=(u,v)$，把 $e$ 去掉。
• 然后我们对 $G\setminus e$（从 $G$ 中删去边 $e$）的任一种染色 $f$。
  1. 对于 $f(u)\neq f(v)$ 的 $f$，则 $f$ 也是 $G$ 的染色。
  2. 对于 $f(u)=f(v)$ 的 $f$，则$f$ 是图 $G\cdot e$ 的染色（把 $G$ 中 $e$ 的端点合并，去掉重边）
• 反之，$G$ 的染色均是 $G\setminus e$ 的使 $f(u)\neq f(v)$ 的染色，$G\cdot e$ 的染色均是 $G\setminus e$ 的使 $f(u)=f(v)$ 的染色。

• 于是，我们定义 $F_G(k)$ 为 $k$ 种颜色对 $G$ 染色的方案数。
• 此时，$F_{G\setminus e}(k)=F_G(k)+F_{G\cdot e}(k)$，即 $F_G(k)=F_{G\setminus E}-F_{G\cdot E}(k)$。
• 对边数归纳可证对于任意的 $G$，$F_G$ 为关于 $k$ 的 $n$ 次多项式。$F_\texttt{n个点，没边}=k^n$ 。
• $F$ 首项系数$=1$，次高项系数$=-|E|$。
• 当 $k<\chi(G)$ 时，$F_G(k)=0$，$(x-k)|F_G(k)$。

5、平面图的定义

• 可以画在平面上，使边与边只在顶点处相交（边可以为曲线或折线）。

6、库拉托夫斯基定理

Kuratowski's Thm

• 一个图是平面图当且仅当 $G$ 无同胚与 $K_5$ 或 $K_{3,3}$ 的子图。
• 同胚：如果两个图 $G_1$ 和 $G_2$ 同构，或经过反复插入（将 $e=(u,v)$ 拆成 $e_1=(u,w),e_2=(w,v)$）或消去 $2$ 度顶点后同构，则称 $G_1$ 与 $G_2$ 同胚。

7、欧拉公式（多面体/平面图）

• 连通图 $G$ 为平面图，$|G|=n,||G||=e,$面数$=f$，则 $n-e+f=2$。

0514下午

1、Ramsey 问题

前置知识

• 图 $G=(V,E)$ ，图的一个边染色指映射 $f:E\rightarrow \{1,2,3,\cdots\}$。
• 对 $\forall e_i,e_j$ ，若 $e_i\cap e_j\neq \varnothing$，则 $f(e_i)\neq f(e_j)$。
• 所需最小色数 $k$ 称为图 $G$ 的边染色数 $\chi'(G)$，显然 $\chi'(G)\geqslant \Delta(G)$。

Viking Thm

• $\chi'(G)\leqslant 1+\Delta(G)$。

Ramsey's Thm

• $\forall s,t\in \mathbb{N}^+$，对 $K_n$ 的边 $2$ 染色，当 $n$ 足够大时，存在红色 $K_s$ 或 蓝色 $K_t$ 子图。
• 最小满足上述条件的 $n$ 称为 Ramsey 数 $r(s,t)$。

$\color{red}{\texttt{Note: }}$

• 常用结论：
  1. $r(s,t)=r(t,s)$，显然。
  2. $\forall x\quad r(x,1)=r(1,x)=1$，证明显然。
  3. $\forall x\quad r(x,2)=r(2,x)=x$，证明显然。
  4. $r(s,t)\leqslant r(s,t-1)+r(s-1,t)$，证明可以对 $s+t$ 归纳，在此略去。
  5. ④的推论：$r(s,t)\leqslant \binom{s+t-2}{s-1}$，显然。

2、简单的 Ramsey 数

$r(3,3)=6$

1. 根据结论⑤，有$r(3,3)\leqslant \binom{4}{2}=6$
2. 证明 $5$ 不可以，请读者自行证明。

$r(3,4)=9$

• 请读者自行证明。

$r(3,5)=14$

1. $r(3,5)\leqslant r(3,4)+r(2,5)=9+5=14$
2. 证明 $13$ 不可以，给出简要思路：循环构造，将 $i-j\equiv \pm 1 \operatorname{or} \pm 5$ 连红边，否则连蓝边。

3、范德瓦尔登定理

Vander Waerden's Thm

• $\forall m\in \mathbb{N}^+,\exists N$，使集合 $\{1,2,3,4,\cdots,N\}$ 的任意 $2$ 染色必定存在同色，长度为 $m$ 的等差数列。
• 上面的表述等价于 $\exists N_1,\{1,\cdots ,N_1\}$ $2$ 染色存在长为 $N$ 的同色等差数列。

4、同色角，异色角方法

• 我们将角的两条边颜色相同的角称为 同色角 ，将角的两条边颜色不同的角称为 异色角 。

• 显然，有同色 $\Delta$ 数 $+$ 异色 $\Delta$ 数 $=\binom n3$。

• 我们考虑顶点在 $v$ 处的 $\Delta$ 。同色角数$=\binom{d_\texttt{红}(v)}2+\binom{d_\texttt{蓝}(v)}2$。异色角数$=d_\texttt{红}(v)\times d_\texttt{蓝}(v)$。所有角数$=\binom{d_\texttt{红}(v)+ d_\texttt{蓝}(v)}2$。

• 整个图 $\sum_{v\in V} \binom{d_\texttt{红}(v)}2+\sum_{v\in V} \binom{d_\texttt{蓝}(v)}2+\sum_{v\in V}d_\texttt{红}(v)\times d_\texttt{蓝}(v)$。

• 即我们可以将 同/异色$\Delta$ 与 顶点的红蓝度 相互转化。

• 若 $1\leq r\leq |S|$，$S_{1..r}=S_{|S|-r+1..|S|}$，则称 $S_{1..r}$ 是 $S$ 的 $border$，长度为 $r$。
• $border$ 的性质：字符串 $s$ 的所有 $border$ 长度排序后可分成不超过 $\log_2 |S|$ 段，每段是一个等差数列。
• 引理 $1$：若存在一个 $border$ 长度为 $k$ ，那么 $|S|-k$ 为 $S$ 的一个周期。
• 引理 $2$：若 $p,q$ 为 $S$ 的周期，且 $p+q\leq |S|$，那么 $\gcd(p,q)$ 也为$S$ 的周期。
• 引理 $3$：$S$ 的所有 $\geq\frac{|S|}{2}$ 的 $border$ 长度组成一个等差数列。

Proof

• 引理 $1$ 是显然的，根据定义，对于 $i+|S|-k\leq |S|$ 即 $i\leq k$，有 $S[i]=S[i+(|S|-k)]$。
• 引理 $2$ [^1]
  • 设 $p < q,d=q-p$
  • 若 $|S|-q\leq i\leq |S|-d$，$S_i=S_{i-p}=S_{i-p+q}=S_{i+d}$。
  • 若 $0\leq i < |S|-q$，$S_i=S_{i+p}=S_{i+q-p}=S_{i+d}$。
  • 那么 $d=q-p$ 也为 $S$ 的周期。由欧几里得算法可知 $\gcd(p,q)$ 也为 $S$ 的周期。
• 引理 $3$ [^2]
  • 设 $S$ 长度最大的 $border$ 的长度为 $n-p,(p\leq \frac{|S|}2)$。
  • 设另外某个 $border$ 的长度为 $n-q,(q\leq \frac{|S|}2)$。
  • 由引理 $2$，有 $\gcd(p,q)$ 是 $S$ 的周期，那么 $n-\gcd(p,q)$ 是 $s$ 的 $border$ 的长度。
  • 则有 $n-p\geq n-\gcd(p,q)$，于是 $\gcd(p,q)\geq p$，即 $p\mid q$。
• 根据引理 $3$，有：
• 考虑更小的 $border$，对其进行按长度的二进制分组，即 $[1,2),[2,4),[4,8)\cdots,[2^k,n)$ 各分为一类。
• 对于在某个类中的 $border$，考虑其最长的，那么剩下的所有 $border$ 一定是最长的那个 $border$ 的 $border$。（正确性证明类似于 $kmp$）。
• 故以最长的 $border$ 为母串（称之为$T$），而类内所有 $border$ 的长度必定 $>\frac{|T|}2$。根据引理 $3$ ，故一类的 $border$ 长度为一个等差数列。
• 故字符串 $S$ 的所有 $border$ 能划分成 $\log_2 S$ 个等差数列。

参考文献：

1. 钟子谦，《串串 解题报告》引理 5.1，2019 年信息学奥林匹克中国国家集训队队员作业
2. 金策，《字符串算法选讲》Border的结构，WC2017课件

• 令 $cut(x,y)$ 为 $x,y$ 的最小割的值。
• 以下的 “连通” ：存在一条 $x,y$ 的路径，其路径上边权最小值非负（等价定义为 $cut(x,y)>0$）。

一个结论

• 将 $x$ 的最小割集割掉之后，那么原图 $y$ 将被分为两个集合。（不考虑原图中与 $x,y$ 不连通的点）
• 一个集合为 $x$ 所在的连通块集合 $A$，一个集合为 $y$ 所在的集合 $B$。

证明

• 假设存在一些点不属于这两个连通块之一。
• 则这些点中必有点和 $A$ 或 $B$ 在原图中有非零边，不妨设有点与 $A$ 在原图中有非零边。
• 那么将这个连通块中与 $A$ 的边全部连回去（即不割这些边），那么 $x,y$ 依旧不连通。
• 而不割这些边后，最小割的值变小了，矛盾。
• 证毕。
• 推论0：对于 $u\in A,v\in B$，有 $cut(u,v)\leq cut(x,y)$，因为 $x,y$ 的最小割也是 $u,v$ 的割。

定理

• 任取不同的三点 $x,y,z$。
• 那么有 $\min(cut(x,z),cut(y,z))\leq cut(x,y)$。

证明

• 若 $cut(x,y)=0$，那么 $cut(x,z),cut(y,z)$ 中也必定有一个为 $0$。
• 若 $cut(x,y)\neq 0$，
  • 不妨设将 $x,y$ 的最小割集割掉之后，$z$ 属于 $x$ 所在的连通块。
  • 那么 $x,y$ 的最小割集同时也是 $z,y$ 的最小割集，即 $cut(y,z)\leq cut(x,y)$。
  • 而 $z$ 属于 $y$ 所在的连通块时，有 $cut(x,z)\leq cut(x,y)$。
• 证毕。

推论1

• 任取不同的三点 $x,y,z$。
• 当 $cut(x,y)$ 满足是 $cut(x,z),cut(y,z),cut(x,y)$ 中最小时，有 $\min(cut(x,z),cut(y,z))=cut(x,y)$。
• 此命题等价于任意三点两两最小割值必有相同。

证明

• 显然。

推论2

• 任取不同的 $k\geq 2$ 个点 $c_1,c_2,\cdots,c_k$，那么有 $\min(cut(c_1,c_2),cut(c_2,c_3),\cdots,cut(c_{k-1},c_k))\leq cut(c_1,c_k)$。

证明

• $cut(c_1,c_k)\geq \min(cut(c_1,c_2),cut(c_2,c_k))$，而 $cut(c_2,c_k)\geq \min(cut(c_2,c_3),cut(c_3,c_k))$，以此类推即证。

推论3

• 任取不同的 $k\geq 3$ 个点 $c_1,c_2,\cdots,c_k$。
• 当 $cut(c_1,c_k)$ 满足是 $cut(c_1,c_2),cut(c_2,c_3),\cdots,cut(c_{k-1},c_k),cut(c_1,c_k)$ 中最小时，那么有 $\min(cut(c_1,c_2),cut(c_2,c_3),\cdots,cut(c_{k-1},c_k))=cut(c_1,c_k)$。
• 此命题等价于任意 $k\geq 3$ 个点两两最小割值必有相同。即最小割值互不相同的边不可能成环。

证明

• 显然。

终极目标

• 任意一张图，任意两点的最小割最多有 $n-1$ 种不同的值。

证明

• 把最小割的值当做边权建立一张完全图。不妨考虑图的任意一棵生成树。
• 依次考虑每一条在树中没出现过的权值的非树边，看它对应的树上的路径必定至少有两条边权值相同（推论3），删除其中一条边后接上这条边。
• 可以发现，做完后可以使所有完全图中权值不同的边都在生成树上，而生成树为 $n-1$ 条边，所以权值不同的边的数量也只有 $n-1$ 条。

最小割树

定义

• 如果对于树上的所有边 $(u,v)$，树上去掉 $(u,v)$ 后产生的两个集合恰好是原图上 $(u,v)$ 的最小割把原图分成的两个集合，且边 $(u,v)$ 的权值等于原图上 $(u,v)$ 的最小割。

构造

• 首先任意选择两个点，跑最小割。
• 那么把图分成的两个部分，由推论0，两个部分之间的最小割是没有影响的。
• 然后继续求解两个部分的最小割树。

性质

• 原图上 $u,v$ 两点最小割就是最小割树上 $u$ 到 $v$ 的路径上权值最小的边。
• 不妨设 $u$ 到 $v$ 的路径上的点（不包括 $u,v$）依次为 $c_1,c_2,\cdots,c_k$。
• 由推论 $3$ ，有 $\min(cut(u,c_1),cut(c_1,c_2),\cdots,cut(c_k,v))\leq cut(u,v)$。
• 而对于每一条边，由推论0，$cut(u,v)\leq cut(u,c_1),cut(u,v)\leq cut(c_1,c_2),\cdots,cut(u,v)\leq cut(c_k,v)$。
• 可得 $\min(cut(u,c_1),cut(c_1,c_2),\cdots,cut(c_k,v))=cut(u,v)$。

[JZOJ5495]【清华集训2017模拟12.09】MiniumCut

• 而这道题其实就是求最小割树，两两点的最小割等于这两点在最小割树上的路径边权最小值。
• 考虑从大到小加入边，新加入一条边时，这条边比之前所有边都要小。
• 如果这条边连接的两个点已经连通了，那么两点路径上的边权最小值 $\min(cut(u,c_1),cut(c_1,c_2),\cdots,cut(c_k,v))\geq cut(u,v)$。
• 又根据推论 $3$，有 $\min(cut(u,c_1),cut(c_1,c_2),\cdots,cut(c_k,v))\leq cut(u,v)$。
• 故 $\min(cut(u,c_1),cut(c_1,c_2),\cdots,cut(c_k,v))=cut(u,v)$，得证。
• 最后需要判断是否合法，因为中间的推论 $3$ 是假设现在满足最小割树的性质的。