[逆向思维] [小清新] P3576

· · 个人记录

链接，思路比较清奇。

思路

显然有个 O(nk) 的做法，不过很难优化的亚子。

不妨逆着想：算出从 u 出发，蚂蚁数量最小、最大为多少才能被吃掉。然后对于叶子二分计算即可。

方程不说了很简单。然后发现这题给出的是关键边，不好处理。

固然可以遍历边的两侧计算，但是有更好方式：拆边为点，去掉该边并让 s,t\to 0 连边。从 0 开始遍历即可。