UOJ Logo WuHongxun的博客

博客

杜教的Dzy loves Chinese证明

2017-10-09 11:40:11 By WuHongxun

因为杜教当年的blog已经不复存在了,所以向杜教重新请教了一边这个证明,把正确的证法在uoj重放一边,方便有兴趣的同学。

要证明的做法就是先随便选一个生成树,然后给每条非树边在2^64范围内随机一个权值(等于是映射到(F_2)^64),然后每条树边的权值等于跨越他的非树边权值的xor,对于每次询问,不连通 iff 删掉的边权的集合线性相关。

这篇blog主要证明给每个非树边分配一位的情况下,有不连通 iff 删掉的边权的集合线性相关。

考虑每次树边等于非树边的xor,其实就是每次一个环上xor了一个值,等于每个点相连的所有边的xor = 0。

每个点的xor =0 iff 树边等于非树边 xor(考虑一个个加入非树边)

考虑一个割,等于若干点的xor起来,所以一个割一定xor = 0。

证完一个方向,另外一个方向如下。

同时xor = 0的时候如果没有割,直接取一个生成树,然后新取的生成树里xor还是为0,所以新的非树边是一组base并且和原来的base大小相同。

所以新的非树边线性无关和存在xor = 0矛盾,证完。

评论

dwjshift
我的证明http://dwjshift.logdown.com/posts/2830435 不知道有没有错。。。有的话求指出。。。

发表评论

可以用@mike来提到mike这个用户,mike会被高亮显示。如果你真的想打“@”这个字符,请用“@@”。