No.386

村々を根付き木 (根を $0$ 番の村とする) と考え, 各村から根の村までの通行料 $V_i$ をあらかじめ計算しておく. これは $V_i = V_j + U_i$ ($j$ は $i$ の親) で計算できる.

行商人ごとに $A, B$ の LCA $L$ を計算して, $A \dots L$, $B \dots L$ をそれぞれ計算して足せばいいので,

$$C(V_A + V_B - 2V_L + U_L)$$

で計算できる.