找错了重心。
以第二篇(@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掉这篇题解.