A+B Problem

众所周知, $A+B problem$ 是一道极难的题

线段树

把 $a$, $b$ 看成一个数组中的两个元素, 很容易想到可以用线段树维护整个区间的和

最短路

假设一个无向图中有 $3$ 个结点, 分别是 $1$, $2$, $3$, 其中 $W_{1, 2} = a$, $W_{2, 3} = b$, 那么 $a + b$ 就是结点 $1$ 到 结点 $3$ 的最短路

二分

二分初始范围为 $(-inf, inf)$, 每次都将 $mid$ 与 $a+b$ 比较, 若 $mid < a+b$, 在有半段区间内寻找, 否则在左半段区间内寻找

LCA

参考最短路解法, 图中有 $3$ 个结点, $2$ 条变, 是一棵树, 所以可以用 LCA 求出树上两点间的距离