1007C步行（树上贡献统计）
http://cplusoj.com/d/senior/p/SS241007C
首先可以发现每条边的贡献为 2 min ( w x , S − w x ) 2\min(w_x,S-w_x) 2min(wx,S−wx)， x x x 为下端的点
考虑现在断一条边，连一条边。我们先不考虑断边，只连边。那么这是一个基环树，不在环上的贡献使容易算的
对于这个环，我们要先找出它的 w w w 变化量。
- 对于绿色区域内一点 p p p， w p w_p wp 变为 w y − w p w_y-w_p wy−wp
- 对于黄色区域内一点 p p p， w p w_p wp 变为 w p − w y w_p-w_y wp−wy
- 对于蓝色区域内一点 p p p， w p w_p wp 变为 w p + w y w_p+w_y wp+wy
然后那个 min \min min 取左还是取右在链上显然满足单调性，直接树上倍增二分即可。处理的时候可以拆成 min ( S − 2 w , 0 ) + w \min(S-2w,0)+w min(S−2w,0)+w 更方便。
原文地址：https://blog.csdn.net/zhangtingxiqwq/article/details/142742718
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！