一个naive的问题,只有一行代码,请放心阅读

P2619 [国家集训队] Tree I

这种情况是默认了黑边白边价值相等,那么选这个减过偏移量的白边形同与选那个黑边,对答案没有影响 (因为`check()`函数的判定是`need<=whitecnt`) 其正确性在于`check()`函数中最后添加的白边等价于黑边,所以二分中我们只记录真正被我们在乎的白边。 (因为二分中答案更新为`ans=sum-need*mid`)
by PotremZ @ 2018-10-11 09:36:45


如果题主觉得我的答案不太严谨,可以在loj上看看这篇证明 [关于 「2012 年国家集训队互测」Tree 问题的回答](https://loj.ac/article/872)
by PotremZ @ 2018-10-11 09:38:20


%%%
by xudaxia @ 2018-10-13 19:36:49


|