关于题解,它……

P3806 【模板】点分治 1

gxy001 @ 2020-07-24 15:50:41

找错了重心。

以第二篇(@Froggy)的为例:

一棵形如下图的树

1 9
9 10
9 8
8 2
2 4
4 7
2 3
3 6
3 5

可以看到在1,9,10,8这个子树中,题解代码找到的重心是8.

经过分析,我发现了原因

get_root(v,0,siz[v]);

在从①出发的搜索中,得到size[8]为7.

而在该子树上找重心时,使用size[8] (值为7)作为了子树的总大小.

事实上,子树总大小为4

但我不会出数据,求大佬利用这个bug hack掉这篇题解.


by AHwhker @ 2020-07-24 15:56:55

%%%%


by houpingze @ 2020-07-24 15:57:15

orz


by dead_X @ 2020-07-24 15:59:24

@froggy (((


by ezoixx130 @ 2020-07-24 16:04:56

@gxy001 http://liu-cheng-ao.blog.uoj.ac/blog/2969


by gxy001 @ 2020-07-24 16:08:26

@ezoixx130 了解了,但我觉得还是要在题解中写一下,不然会误导像我这样的蒟蒻的


by 滑稽的小宫 @ 2020-08-28 07:48:51

gxy大佬orz%%%


|