IOI2018 高速公路收费

Sometimes I see a dying bird fall to the ground

非常好的一道题，Subtask 设置的很好，仔细思考跟着做就能推出来最终做法

一棵树，并且确定了一条边，且点数 $\le 100$

先问一下 $S,T$ 的距离

然后分别试一下每条边是否在路径上即可

比 Subtask 1 的点数变多了

考虑以 $0$ 为根，处理出深度，那么 $T$ 一定在 $\mathrm{dep}=dis(S,T)$ 上

那我们可以二分这些边，每次把一半置成 $1$ 如果变动了，说明在这半边

链，直接二分即可

仅仅保证了树，但是我们可以二分找到一个边在 $S \to T$ 上，然后删去这条边，在分别以这两个端点为根的树上做 Subtask 2

似乎没啥能用的性质

现在能做树了，考虑把图转成树来做

我们希望可以找到一种方法使得改边树上的状态时最短路不会经过图上，实际上也很简单，先类似 Subtask 4 找出来边，然后两个端点跑 bfs，找出最短路，然后把非 bfs 树的边全都设为 $B$ 这样无论怎么改都只会走树边

找到第一条在 $S \to T$ 需要 $\log_2m$ 然后两棵树分别二分需要 $2\log_2n$

不会超过 $50$