由于题目过多，只放几道重要的。。。
T1
• A 国有 \(n\) 座城市，编号从 \(1\) 到 \(n\)，城市之间有 \(m\) 条双向道路。每一条道路对车辆都有重量限制 \(z\)，简称限重。
• 现在有 \(q\) 辆货车在运输货物，司机们想知道每辆车在不超过车辆限重的情况下，最多能运多重的货物。
• \(1 ≤ n \leq 10^4\)，\(1 ≤ m \leq 5 \cdot 10^4\)，\(1 ≤ q ≤ 3 \cdot 10^4\)，\(0 ≤ z ≤ 10^5\)。
Solution
• 实现 \(x\) 到 \(y\) 的所有路经中，路径上边的最小值最大。
• 容易想到把图转化为最大生成树，树上两点的路径就是所有路径中，最小值最大的路径。
• 树上两点间的最小路径值，容易想到用倍增计算。
T2
• 有一个树形的水系，由 \(N−1\) 条河道和 \(N\) 个交叉点组成。
• 每条河道都有一个容量，连接 \(x\) 与 \(y\) 的河道的容量记为 \(c(x, y)\)。
• 有一个节点是整个水系的发源地，可以源源不断地流出水，我们称之为源点。
• 除了源点之外，树中所有度数为 \(1\) 的节点都是入海口，可以吸收无限多的水，我们称之为汇点。
• 流入该点的河道水量之和等于从该点流出的河道水量之和。
• 整个水系的流量就定义为源点单位时间发出的水量。
• 在流量不超过河道容量的前提下，求哪个点作为源点时，整个水系的流量最大，输出这个最大值。
• \(N \leq 2 \cdot 10^5\)，数据保证结果不超过 \(2^{31}−1\)。
Solution
• 定义 \(f_i\) 表示以 \(i\) 为根的子树的最大流量。
\[ f_n = \sum_ {v \in son(u)} \begin{cases} \min (f_v, w(u, v)) & deg_v > 1 \\\\ w(u, v) & deg_v = 1 \end{cases}\]• 接下来考虑换根 \(dp\)
• 对于原本以 \(u\) 为根，转为以 \(v\) 为根，分类讨论。
- 如果 \(deg_u = 1\)，\(f_v += w(u, v)\)。
- 如果 \(deg_v = 1\)，\(f_v = \min(fu − w(u, v),w(u, v))\)。
- 否则，\(f_v += \min(fu − \min(fv ,w(u, v)),w(u, v))\)。
T3
题目
• 一所学校前一段时间买了第一台计算机（所以这台计算机的 \(ID\) 是 \(1\)）。
• 近年来，学校又购买了 \(N−1\) 台新计算机。
• 每台新计算机都与之前买进的计算机中的一台建立连接。
• 现在请你求出第 \(i\) 台计算机到距离其最远的计算机的电缆长度。
• \(1 ≤ N ≤ 10000\), 电缆总长度不超过 \(10^9\)。
Solution
• 先考虑如何计算第 \(1\) 台计算机到距离其最远的计算机的电
缆长度。
• 以第 \(1\) 台电脑为根，计算树的最大深度即为答案。
• 计算每个点的答案，还是换根 \(dp\)。。。
• 下文中，以 \(son_u\) 表示 \(u\) 的重儿子，\(d1_u\) 表示以 \(u\) 为根的子树的最大深度，\(d2_u\) 表示以 \(u\) 为根的子树的次大深度。
• 原本以 \(u\) 为根，换到以 \(v\) 为根，分类讨论。