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%%%