考虑倍增。

$f(i,k), g(i,k)$ 分别表示从 $i$ 出发，走 $2^k$ 步经过的边权最小值和边权和。一开始 $f(i,0)=g(i, 0)=w_i$。

为了方便处理，我们定义 $to(i, k)$ 表示从 $i$ 出发，走 $2^k$ 步走到的点。$to(i, k)$ 显然是容易处理的。根据 $to(i, k)$ 预处理 $f(i, k), g(i, k)$ 即可。

时间复杂度 $O(n \log ⁡k )$。