题目理解

我们有一棵以节点1为根的树，表示一个管道系统。每个边（管道）有两个属性：

• $X_i$：流量百分比（从父节点流向子节点的液体比例）
• $T_i$：是否"开挂"（1表示开挂，0表示不开）

特殊机制：如果管道开挂（$T_i = 1$），那么流经该管道的液体会变成原来的平方。

蚂蚁只住在叶子节点，每个叶子节点有需求 $K_i$（非叶子节点 $K_i = -1$）。

我们需要找到最小的 $L$，使得在根节点倒入 $L$ 升液体时，所有叶子节点获得的液体量至少等于它们的需求 $K_i$。

关键观察

1. 问题的非线性特性

由于"开挂"管道的平方操作，系统变得非线性：

• 普通管道：输出 = 输入 × $X_i/100$
• 开挂管道：输出 = (输入 × $X_i/100$)²

这意味着液体在流动过程中可能被放大（当输入 > 1时）或缩小（当输入 < 1时）。

2. 逆向思维

直接计算从根节点到叶子节点的流量很复杂，因为平方操作使得关系非线性。

更好的方法是：从叶子节点的需求反向推导根节点的最小需求。

算法设计

1. 二分答案框架

由于我们需要最小化 $L$，且问题具有单调性（如果 $L$ 可行，那么所有大于 $L$ 的值也可行），可以使用二分答案：

1. 确定二分范围：$[0, 2 \times 10^9]$（题目保证）
2. 对于中点 $mid$，检查 $mid$ 升液体是否足够满足所有叶子节点需求
3. 根据检查结果调整二分区间

2. 可行性检查

对于给定的根节点液体量 $L$，我们需要检查是否能满足所有叶子节点的需求。

关键思路：从叶子节点向根节点反向计算每个节点的"需求"。

定义 $req[u]$：为了满足节点 $u$ 的所有后代叶子节点的需求，节点 $u$ 至少需要获得多少液体。

3. 反向需求计算

采用树的后序遍历（自底向上）：

1. 叶子节点：$req[u] = K_u$（直接需求）
2. 内部节点：
   • 对于每个子节点 $v$，通过边 $(u,v)$ 计算：
     • 如果 $T_i = 0$（普通管道）：$v$ 需要 $req[v]$，那么 $u$ 需要至少 $req[v] \times \frac{100}{X_i}$
     • 如果 $T_i = 1$（开挂管道）：$v$ 需要 $req[v]$，那么 $u$ 需要至少 $\sqrt{req[v] \times \frac{100}{X_i}}$
   • $u$ 的总需求是所有子节点需求中的最大值（因为液体可以同时流向多个子节点）

数学推导：

• 普通管道：$output = input \times \frac{X_i}{100}$ ⇒ $input = output \times \frac{100}{X_i}$
• 开挂管道：$output = (input \times \frac{X_i}{100})^2$ ⇒ $input = \sqrt{output \times \frac{100}{X_i}}$

4. 算法步骤

1. 二分查找：

   • 初始化 $low = 0$, $high = 2 \times 10^9$
   • 当 $high - low > \epsilon$（如 $10^{-6}$）时：
     • $mid = (low + high) / 2$
     • 如果 $check(mid)$ 返回真：$high = mid$
     • 否则：$low = mid$

2. 可行性检查函数 $check(L)$：

   • 从叶子节点开始后序遍历
   • 对于每个节点 $u$：
     • 如果是叶子节点：$req[u] = K_u$
     • 如果是内部节点：$req[u] = \max\limits_{v \in children(u)} f(req[v], X_{uv}, T_{uv})$
       • 其中 $f(output, X, T) = \begin{cases} output \times \frac{100}{X} & \text{if } T = 0 \\ \sqrt{output \times \frac{100}{X}} & \text{if } T = 1 \end{cases}$
   • 检查 $req[1] \leq L$（根节点的需求不超过实际倒入量）

正确性分析

1. 单调性

如果 $L$ 可行，那么任意 $L' > L$ 也可行，因为我们可以提供更多液体。

2. 需求计算的正确性

• 叶子节点：需求就是 $K_i$
• 内部节点：必须满足所有子节点的需求，因此取最大值
• 管道计算：精确反推了液体流动的关系

3. 平方操作的影响

开挂管道实际上创建了一个"放大器"：

• 当输入 > 1时：输出被放大
• 当输入 < 1时：输出被缩小

这解释了为什么一个节点的流出液体可能大于流入液体。

复杂度分析

• 二分查找：$O(\log(\frac{2\times 10^9}{\epsilon}))$ ≈ 50次迭代
• 每次可行性检查：$O(N)$ 后序遍历
• 总复杂度：$O(N \log(\frac{2\times 10^9}{\epsilon}))$，对于 $N \leq 1000$ 非常高效

实现细节

1. 精度处理

• 使用 double 类型进行计算
• 二分终止条件：$high - low > 10^{-6}$
• 输出时控制小数点后位数

2. 特殊边界

• 确保平方根计算时参数非负
• 处理百分比计算的浮点误差

3. 树结构存储

• 使用邻接表存储树结构
• 记录每个节点的父节点和子节点

总结

这道题的核心在于通过逆向思维和二分答案，将复杂的非线性流量分配问题转化为可计算的形式：

1. 问题转化：将最小化问题转化为可行性判断问题
2. 逆向计算：从叶子需求反向推导根节点需求
3. 非线性处理：正确处理平方操作的数学关系
4. 二分优化：利用单调性快速找到最优解

这种"二分答案 + 逆向计算"的思路在解决带约束的优化问题时非常有效，特别是当正向计算复杂而逆向计算简单时。