萌新看不懂题解,求助
查看原帖
萌新看不懂题解,求助
223392
Belarus楼主2020/7/21 15:46

这一篇题解里面,这段话有些看不懂

c点产生贡献放在桶的deep[c]位置,计算b点获得的贡献时当然是从bucket1[deep[b]+w[b]]位置获取,于是得到1个贡献,你发现a结点也是用的同一个桶,这个还好,因为c确实给他做了贡献,可是e点呢?他是不应该获得贡献的!既然我会给和我无关的结点做贡献,那么其它无关的结点难免也会给我做贡献!
问题总结一下,对于一个点P来说,究竟哪些点在桶里面产生的贡献才是有效的。
答案是:以P为根递归整颗子树过程中在桶内产生的差值才是有效的

比如

既然我会给和我无关的结点做贡献,
那么其它无关的结点难免也会给我做贡献!
以P为根递归整颗子树过程中在桶内产生的差值才是有效的

为什么是这样?什么叫“在桶内产生的差值”

另外,这个题解是通过建边的方式代替集合(并查集)吗?

2020/7/21 15:46
加载中...