关于题解,它……
查看原帖
关于题解,它……
55707
gxy001楼主2020/7/24 15:50

找错了重心。

以第二篇(@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掉这篇题解.

2020/7/24 15:50
加载中...