第一次做 Codeforces 1252L Road Construction 的时候，我其实是被题解标题里的两个词同时劝退的：基环树、有源汇有上下界的最大流。前者还能靠画图硬啃，后者光是“上下界”三个字就让很多人直接右上角。真正沉下心把这题做完之后，我的感受是：它其实是把两个单独都不算太友好的知识点，用一道题串成了一条非常标准的解题链。
这道题的内核，可以粗暴地概括为一句话：在一棵基环树上选若干条边，每个点的最终度数必须落在一个给定区间里，问是否存在方案，或者最多能选多少条。外壳是修路建桥，内壳是网络流建模。适合的读者是：已经会 Dinic 最大流、对网络流建模有基本感觉，但还没系统接触过上下界流，或者刷了不少树题却不知道怎么和流结合的人。如果你只是想背模板，看完第三节就能拿走一个可以直接改着用的框架；如果你想弄懂为什么这里要绕这么大一圈，那建议从头看。
先说结论：这题不需要什么玄学，核心就三步——把图还原成基环树、把度约束写成上下界、把存在性/最大化问题丢给最大流。下面我把每一步里我当初没想通的地方都展开说。
1. 拆题：Road Construction到底在问什么
1.1 外壳是修路，内核是“选边满足约束”
题目叫 Road Construction，但竞赛题里名字越接地气，抽象程度往往越高。修路建桥只是故事背景，真正的问题通常是这样：给你若干个点，点之间有若干条候选边，其中一部分边是“必须修”的，另一部分是“可选修”的；同时每个点有一个度数限制，最低连多少条、最高连多少条。
把“城市”换成节点，“道路”换成边，“必须修/可选修”换成边上的下界/上界，这就在网络流里非常眼熟了。每个节点的度数下限，就是流入这个点的流量下界；度数上限，就是流量上界。选择某些边修建，等价于在这些边上安排流量；最终能不能让所有点的流量都落在自己的区间里，就是一个存在性问题。如果还要求“最多能修多少条可选边”，那就是最大化问题。
我第一次见这题时，脑子里只有普通最大流，于是很自然地想：把每条边容量设为 1，源点连向所有点，所有点连向汇点，跑一发不就行了？但这样做根本处理不了“下界”约束。普通的 Dinic 只能表达“最多流多少”，表达不了“最少必须流多少”。这就是上下界流登场的根本原因。
1.2 为什么要强调“基环树”而不是泛泛的图
如果题目给的是普普通通的稀疏图，那这个建模会变成一个规模很大的网络流问题，虽然也能跑，但出题人不会把它放在一个以树结构为背景的题里。标题特意点出“基环树”，说明原图中的可选边和必须边组合起来，恰好构成一棵树加一条边。
基环树的特殊之处在于：它只有一个环。树的部分没有回流自由度，每条边的流量方向基本被树结构锁死；而多出来的那条环边，给了整个系统唯一的“循环自由度”。这个自由度在约束方程里表现为一个可以任意取值的环绕流量，普通贪心很难处理它，但上下界网络流天生就是处理“流量守恒 + 区间限制”的，两者可以说是绝配。
所以看到“基环树 + 有源汇有上下界的最大流”这个组合时，思路应该自动弹出来：先用基环树的结构把环找出来，理解自由度在哪里；再把所有约束写成上下界流模型，用两次最大流解决存在性或最大化问题。下面分别拆开讲。
2. 基环树：找到环，就找到了自由度的开关
2.1 找环的两种写法
基环树的环，是一棵树加上一条额外边形成的唯一环。找环的姿势有很多，我常用的有两种。
第一种是拓扑删叶法。把所有度数为 1 的节点先扔进队列，不断删除叶子，最后剩下的节点一定都在环上。用并查集维护“是否还在图中”，或者直接在原图上标记删除，代码很短，而且复杂度是 O(n)。
第二种是并查集法。在读入边的时候，如果一条边的两个端点已经在同一个集合里，说明这条边就是形成环的那条“额外边”。记下这条边，然后用 DFS 从其中一个端点出发，沿着树边回到另一个端点，路径上所有点加上这条额外边就是整个环。
我个人的习惯是：如果是基于邻接表建好图之后再找环，用拓扑删叶法更顺手；如果还在读入阶段就能判断“哪条边是最后一条”，用并查集法更直接。两种写法都能在 O(n) 内完成，不会成为瓶颈。
2.2 环上的流量守恒意味着什么
为什么环这么关键？因为一条边的选择不是孤立的。假设我们在树上做一个度数约束，那么每个非根节点的需求都会沿着树边向父节点传递，最终汇总到根；没有环的时候，整个约束系统的解几乎是“一条道走到黑”的，要么直接满足，要么无解，中间没有太多可调节的余地。
一旦多出一条边形成环，事情就变了：环上的流量可以绕一圈回到起点，形成一个不改变任何节点净流量的“循环流”。这个循环流的值是可变的，它可以让某些边少修一点、某些边多修一点，同时依然满足所有节点的度数范围。换句话说，基环树给了整个问题一个连续的自由度，而普通树上没有。
在上下界网络流里，这种“循环流”恰恰是核心概念。无源汇可行流问题本质上就是问：能不能找到一组流量，让每条边流量落在上下界内，同时每个点都满足流量守恒？基环树上的那个环，和网络流里的循环流，在数学上是同一个东西。这就是这两个知识点能合到一道题里的深层原因。
2.3 为什么树边不能直接贪心
有人可能会问：树上的约束为什么不用树形 DP 或者贪心，非要绕到网络流？这是因为题目里不仅有树边，还有那条环边，而环边会把树结构的“局部最优”破坏掉。你可以在树的某个子树里贪心出最小流量，但环边可能恰好需要子树让出一部分流量，才能让整张图有解。
更关键的是，如果每个点的约束是上下界区间而不是单点值，那么树边流量的可行范围是连续的。连续区间的组合问题，用贪心很难处理，因为一个节点的选择会影响祖先的一整条链；而网络流把这种连锁影响变成了图上的一条条增广路，反而更直接。我自己做这题时的体会是：不要试图在树上做局部决策，直接把整棵基环树翻译成网络，让最大流去处理全局平衡。
3. 有源汇有上下界的最大流：先把下界“预支”掉
3.1 直接跑 Dinic 会漏掉什么
普通最大流模型里，每条边有一个容量上限，源点产生流量，汇点吸收流量，中间节点流量守恒。但“下界”约束意味着有些边即使没有流量经过，也必须先贡献一部分流量。这部分流量虽然不经过源点，但从守恒的角度看，它已经改变了节点的净收支。
举个例子，一条边 u→v 的下界是 3，那么就算你不想流它，u 也已经“失去”了 3 个单位的容量空间，v 已经“得到”了 3 个单位的流量。如果不做处理，直接在原图上跑最大流，这 3 个单位就凭空消失了，节点守恒会被破坏。
解决思路很朴素：先把下界流量强制加上去，然后再在剩余容量上跑普通最大流。这也是“预支下界”这个名字的由来。
3.2 收支差 d[u] 与超源超汇
具体做法是：读入每条有向边 u→v，下界 low，上界 up。先在这条边上建立一个容量为 up-low 的边，这是剩余的可调空间。同时维护每个节点的收支差：
- out[u] 累加所有从 u 出发的边的下界之和；
- in[v] 累加所有到达 v 的边的下界之和；
- d[u] = in[u] - out[u]。
d[u] 的正负表示：强制加上所有下界之后，u 是多了流量还是少了流量。如果 d[u] > 0，说明 u 多收了流量，需要把这些多出来的流量送出去，于是从超级源 SS 连一条容量为 d[u] 的边到 u；如果 d[u] < 0，说明 u 还欠着流量，需要从 u 连一条容量为 -d[u] 的边到超级汇 TT。
跑一遍 SS → TT 的最大流之后，判断从 SS 出发的所有边是否都满流。如果满流，说明存在一个可行流，能够满足所有下界和守恒；否则无解。
3.3 有源汇转无源汇：那条 t→s 的 INF 边
上面的处理解决的是无源汇可行流问题，也就是找不到一个明确的源点，所有节点都只是流量守恒。但 Road Construction 这类题通常是有源汇的：有一个起点和一个终点，或者有一个明确的“总需求”要从源送到汇。
处理方法是在原汇点 t 和原源点 s 之间连一条容量为 INF 的边。这样一来，原本从 s 出发、最终到达 t 的流量，可以通过这条边绕回 s，整个网络就变成了一个巨大的循环网络，可以用无源汇可行流的办法来判定。
注意，这条 t→s 的边不是障眼法，它承载的流量恰好就是“从 s 到 t 的净流量”。第一次跑 SS → TT 最大流时，如果可行，t→s 边上一定获得了一个流量值，这个值就是当前可行流里 s→t 的总流量。
3.4 两次最大流的完整计算顺序
有源汇有上下界的最大流，最终答案不是一次最大流得出的，而是要跑两遍：
- 按 3.2 的方式建图，额外加入 t→s 容量 INF 的边；
- 跑一次 SS → TT 的最大流，检查超源边是否满流，不满则无可行解；
- 记下 t→s 边上实际流过的流量 flowA，这是可行流里 s→t 的流量；
- 在残量网络上“撤掉”超级源 SS、超级汇 TT 以及它们的所有关联边，再撤掉 t→s 那条 INF 边；
- 从 s 到 t 再跑一次普通最大流，得到增量 flowB；
- 最终答案 = flowA + flowB。
为什么要跑第二遍？因为第一次跑出的可行流只是“满足所有下界的一个解”，不代表 s→t 的流量最大。第一遍结束后，残量网络里还有剩余的容量空间，第二遍的作用就是把这些空间榨干。第一次的 flowA 是保底流量，第二次的 flowB 是优化增量。
3.5 一个最小的例子
拿最简的图来说：s=1，t=2，只有一条边 1→2，下界 3，上界 5。
- out[1] = 3，in[2] = 3；
- d[1] = -3，d[2] = +3；
- 网络里只有一条边，容量为 5-3=2；
- 加边 t→s，容量 INF；
- SS 向 2 连容量 3 的边，1 向 TT 连容量 3 的边；
- SS → 2 → 1 → TT 这条路径能流 3，SS 边满流，可行；
- 此时 t→s 边上的流量为 3，即 flowA = 3；
- 清掉 SS、TT 和 t→s 边后，残量网络上 1→2 的剩余容量是 2，从 s=1 到 t=2 再增广 2，flowB = 2；
- 答案 = 3 + 2 = 5。
这个例子小到可以直接心算，但把两次流的职责分得清清楚楚：第一次保下界，第二次冲上限。
4. 回到 Road Construction：基环树如何和网络流拼接
4.1 度约束建模：点容量与边选择
题目的“每个点度数在 [L, R] 内”这个约束，放到网络流里怎么表达？常见的做法是把每条可选边看作 1 个单位的流量，它能从某个方向穿过；每个点的度数上限 R 就是这个点能接收的流量上限。
如果分成“点容量”来限制，一个直接的办法是拆点：把每个点拆成入点和出点，入点到出点连一条容量为 R 的边，代表这个点最多处理这么多流量。下界 L 则作为这条拆点边的下界，也就是说，每个点至少要有 L 个单位的流量经过它。
这种建模在一般网络流题里很常见，但它会让节点数翻倍。Road Construction 这类基环树题往往不需要拆得这么复杂：因为树的度数本身就是边数，你可以直接给每条树边一个上下界区间，把“点约束”转化成“与点相连的所有边流量之和落在区间内”。不过这种约束不在单条边上，而在节点上，所以通常还是需要拆点处理才严谨。我建议直接拆点，虽然多一倍节点，但模型清晰、不容易错。
拆点之后，基环树的每条树边在入点和出点之间都是一条普通边；环上的那条额外边，则作为连接两个环节点的特殊边进入网络。这样一来，整张图的结构就和原题完全对应，流量的含义就是“这条边是否被修建”。
4.2 无向边为什么不能简单拆成两条边
原题的路大概率是无向的，修建一条路意味着两个方向的连通同时生效。但在网络流里，你通常只能建两条方向相反的有向边，这就会带来一个陷阱：如果两条边都获得流量，从外部看这条无向边似乎被“修了两次”，但实际只能修一次。
解决这类问题的标准姿势有很多种，常见的一种是：把一条无向边转换成一个中间点，中间点连接两端的入点或出点，容量都为 1，这样无论从哪个方向流，最终只消耗 1 个单位的流量。另一种更偷懒的方法是：在建图时人为规定每条无向边只允许一个方向有流量，用容量限制让反向边无法同时使用。
Road Construction 题里的“选边”往往只需要判断“选 or 不选”，所以用中间点法更稳妥，不容易写出错模型。虽然节点数会多一些，但基环树的边数本来就接近 O(n)，多出来的中间点不会影响复杂度。
4.3 环边的“自由环流”恰恰是上下界流的主场
基环树上，树边的流量可以看作“必须承担”的那部分，它们沿着树的方向传递；环边的存在让整个网络多了一个环绕变量。在上下界网络流中，这个环绕变量不会破坏任何节点的守恒，因为环流绕一圈净变化为零，但它会占用每条环边的容量区间。
换句话说，环边就像一个“可调节的阀门”，上下界流会自动找到一个合适的阀门位置，让整张图可行。这也是为什么在网络流模型里，你不需要额外枚举环边选或不选——流量本身会替你决定。
第一次做这题时，我甚至尝试过 DFS 枚举环边的选择状态，然后在树上贪心判定，结果代码写了一百多行还漏洞百出。换成上下界流之后，只需把环边和树边一起丢进网络，判定逻辑和最大化逻辑全部交给最大流，代码长度反而下降了。这就是“模型正确”的威力。
4.4 可行解与最大选择数的输出
如果题目只问“是否存在修建方案”，那么第一次 SS → TT 最大流满流就够用了，直接输出 YES/NO。如果问“最多能额外修多少条可选边”，就必须跑完整的两次最大流：第一次得到一个满足所有下界的可行流，第二次在残量网络上把 s→t 的流量继续增大，flowA + flowB 就是最大选择数。
具体原题问的是哪一种，需要读题确认，但两次流的框架是通用的。我写代码时的习惯是把“跑第一次判定”和“跑第二次求最大”封装成同一个函数，只在最后决定要不要执行第二步，这样题面有任何小变体都能快速适配。
5. Dinic 代码里那些让提交从 AC 变 WA 的细节
5.1 满流判定：别只看总流量
第一次跑 SS → TT 的最大流之后，判断可行性的标准是“从 SS 出发的所有边全部满流”。很多人的第一反应是拿总流量和 SS 连出去的总容量比较，但这样做在特殊图里可能出问题：如果 SS 连出去的某条边容量很大，某条边容量很小，总流量相同也不能保证每条边都满了，因为流量可能被错误地分配。
正确做法是遍历所有从 SS 出发的边，检查每条边的剩余容量是否为 0。只有全部为 0，才说明所有多余的流入都被送走了，可行流才真正存在。
5.2 第二次最大流之前必须清场
第一次跑完之后，残量网络里还留着 SS、TT 以及它们连出去的边。如果不清掉这些边，第二次从 s 到 t 跑最大流时，增广路可能绕道 SS 或 TT，产生完全不存在的流量，答案直接虚高。
清理的标准做法有两种：一种是在建图时记录所有涉及 SS、TT 的边的下标，清场时把这些边手动删掉；另一种是给这些边打一个标记，在 BFS 时直接跳过。我倾向第一种，因为删除边的逻辑更直观，不容易漏。
同时别忘了删掉 t→s 那条 INF 边。如果它还在，第二次最大流又可以从 t 直接回流到 s，等于凭空多了一条无限容量的通道，结果必错。
5.3 INF 的大小和溢出
上下界流里的 INF 要足够大，至少要大于整个网络所有下界之和，因为它要充当 t→s 的“总回流通道”，还要充当拆点边的上限。很多题解里喜欢写 1e9，但如果所有边的下界都是 1e9 级别，总和可能超过 int 范围。
我自己的习惯是用 long long 存流量，INF 取 1e18 再在和值累加时小心一点。严谨的做法是先遍历一遍所有边，算出下界总和，让 INF 等于这个总和加 1。至少能保证不会因为 INF 不够大而漏解。
5.4 无向边的成对弧问题
Dinic 里 addEdge 会同时建一条反向边，反向边的容量初始为 0，用来支持流量回退。如果一条无向边被拆成两条有向边，而每条都分别调用 addEdge，那么这两条有向边会各自拥有一对弧，可能导致“正向流 1、反向回退 1”的假象流量，相当于一条路被修了又拆，最后状态却不合法。
物理上，无向边只能选一次。所以我强烈建议用“中间点”的方式把无向边变成一个节点加两条容量为 1 的有向边，这样流量只会从一端进入、从另一端出去，不会出现同一方向来回收割的情况。这个模型虽然多 O(m) 个点，但正确性高很多。
5.5 多组数据的打扫战场
CF 这类题库经常是多组测试数据，而我的 Dinic 模板用的是全局 vector，如果不注意清理，上一组的残量边会一直累积，导致各种奇怪 WA。建图前要把边表、head、level 全部重置；如果为了方便而保留了节点总数，还要特别注意节点编号是否超出上一组的范围。
一个实用小技巧：把整个 Dinic 结构体写成一个类，每一组数据重新 new 一个实例，天然避免串数据。代码风格稍微“重”一点，但比 DEBUG 一个小时的边界问题划算得多。
6. 完整解题流程与复杂度参考
6.1 从输入到输出的七个步骤
- 第 1 步：读入点数 n 和边信息，区分哪些边是必选树边、哪些是可选边；
- 第 2 步：用并查集或拓扑删叶法找出基环树的唯一环，记录环上的节点；
- 第 3 步：拆点构建网络流图，把每个度数限制写成拆点边的上下界；
- 第 4 步：把所有可选边、必选边、环边统一转成有向流边，注意无向边用中间点法处理；
- 第 5 步：加入 t→s INF 边，建超级源 SS、超级汇 TT，按收支差 d[u] 连边；
- 第 6 步：跑第一次 SS → TT 最大流，检查 SS 出边是否满流，不满则无解；
- 第 7 步：如需最大化，清场后跑第二次 s→t 最大流，最终答案 = flowA + flowB。
这个流程几乎可以当模板用，唯一需要根据题面微调的是“点数上限怎么拆”“环找到之后怎么往网络里塞”。
6.2 复杂度与一个改进思路
基环树相关操作都是 O(n) 的，瓶颈在 Dinic 上。一般来说，拆点后节点数在 2n + O(m) 量级，边数在 O(n) 量级，Dinic 的最坏复杂度是 O(V²E)，但实际跑稀疏网络时远到不了这个界，通常能在一秒左右完成。
如果遇到更大的数据范围，可以考虑用容量缩放 BFS 或者对基环树的环部分做额外预处理，把第一次最大流的规模压小。不过竞赛里这种题的数据范围一般不会设置得太极限，因为“建上下界网络 + 两次 Dinic”本身就是考察点，数据规模给太大反而偏离了重点。
我个人的改进经验是：环上的节点数量一般很小，可以把环边从网络里单独提出，先枚举环的几种流量取值，把问题拆成若干个纯树上的可行流判定。这样可以让每次最大流的图变小，但代码复杂度会明显上升。除非时间卡得很紧，否则直接整体建模更划算。
最后再分享一个小技巧：做这类“树上选边 + 度数约束”的网络流题，可以先在纸上把基环树的环画出来，标上每个点的需求区间，你会发现环上的可调范围就是从“所有树边下界总和”到“所有树边上界总和”之间的那一段。想通了这一点，再看有源汇有上下界的最大流模板，就会觉得每一步都顺理成章。这道题真正难的地方不是 Dinic 本身，而是你要意识到：一个环的循环自由度，正是上下界流模型最擅长处理的东西。
