P4069 [SDOI2016] 游戏

Alice 和 Bob 在玩一个游戏。 游戏在一棵有 $n$ 个点的树上进行。最初，每个点上都只有一个数字，那个数字是 $123456789123456789$。 有时，Alice 会选择一条从 $s$ 到 $t$ 的路径，在这条路径上的每一个点上都添加一个数字。对于路径上的一个点 $r$，若 $r$ 与 $s$ 的距离是 $dis$，那么 Alice 在点 $r$ 上添加的数字是 $a\times dis+b$。 有时，Bob 会选择一条从 $s$ 到 $t$ 的路径。他需要先从这条路径上选择一个点，再从那个点上选择一个数字。 Bob 选择的数字越小越好，但大量的数字让 Bob 眼花缭乱。Bob 需要你帮他找出他能够选择的最小的数字。

无

无

测试点 1 ~ 2：$ n \leq 10 $，$ m \leq 10 $，$ | a | \leq 10000 $； 测试点 3 ~ 4：$ n \leq 1000 $，$ m \leq 1000 $，$ | a | \leq 10000 $； 测试点 5：$ n \leq 100000 $，$ m \leq 100000 $，$ a = 0 $，树是一条链； 测试点 6 ~ 7：$ n \leq 100000 $，$ m \leq 100000 $，$ a = 0 $； 测试点 8：$ n \leq 100000 $，$ m \leq 100000 $，$ a = 1 $，树是一条链； 测试点 9 ~ 10：$ n \leq 100000 $，$ m \leq 100000 $，$ a = 1 $； 测试点 11 ~ 13：$ n \leq 100000 $，$ m \leq 100000 $，$ | a | \leq 10000 $，树是一条链； 测试点 14 ~ 20：$ n \leq 100000 $，$ m \leq 100000 $，$ | a | \leq 10000 $。 对于所有数据，$0\le w, |b|\le 10^9$。