9476

原题 人类智慧题！！！ 假如没有地铁，这题就是一个非常典型的计算贡献的题。我们对每一条边看他左右子树中通过的客流量多少，对于一个边权为 \(w\) 的边，他的贡献显然为 \(w \times S_1 \times S_2\) ，其中 \(S_1,S_2\) 为当前边把树分成左右两部分的子树大小 现在 ......