1007C步行（树上贡献统计）

本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/142742718

http://cplusoj.com/d/senior/p/SS241007C

首先可以发现每条边的贡献为 $2\min(w_x,S-w_x)$ ， $x$ 为下端的点

考虑现在断一条边，连一条边。我们先不考虑断边，只连边。那么这是一个基环树，不在环上的贡献使容易算的

对于这个环，我们要先找出它的 $w$ 变化量。

• 对于绿色区域内一点 $p$ ， $w_p$ 变为 $w_y-w_p$

• 对于黄色区域内一点 $p$ ， $w_p$ 变为 $w_p-w_y$

• 对于蓝色区域内一点 $p$ ， $w_p$ 变为 $w_p+w_y$

然后那个 $\min$ 取左还是取右在链上显然满足单调性，直接树上倍增二分即可。处理的时候可以拆成 $\min(S-2w,0)+w$ 更方便。