神蛙题解可能有锅（如果我错了轻喷）

P3806 【模板】点分治 1

C20203030 @ 2020-12-03 08:47:53

第二篇题解，我在写点分树模板的时候发现了这种写法有锅。

比如对于下面的数据（点分树样例）：

8 1

1 2 1

1 3 1

2 4 1

2 5 1

3 6 1

3 7 1

3 8 1

这样神蛙会把 1 划分成第二层的根（第一层根是3）

各位可以自行试一试，眼见为实。

而且我发现了他代码中具体的错误：


void solve(int u){
    vis[u]=true;
    calc(u);
    for(re int i=head[u];i;i=edge[i].nxt){
        int v=edge[i].to;
        if(vis[v])continue;
        root=0;
        get_root(v,0,siz[v]);
        solve(root);
    }
}

因为siz[v]不是真的子树大小，所以锅了

希望能有人看看是不是真的有问题，毕竟神蛙的题解很多人在看，本人是蒟蒻，如果我错了轻喷

by 星空舞涵 @ 2020-12-03 08:52:06

可以问问神蛙

by watermonster @ 2020-12-03 08:54:24

@C20203030 有证明，不过我看不太懂

by C20203030 @ 2020-12-03 08:56:17

我觉得还是换一种写法比较合适吧，搞一个函数去统计子树大小来替换上面的 siz[v]

by watermonster @ 2020-12-03 08:58:22

@C20203030 应该对得到的重心重新跑一次get_root就行了吧？

by C20203030 @ 2020-12-03 09:01:34

@watermonster 可能是的

by gxy001 @ 2020-12-03 09:01:58

早就有人发现了，复杂度是对的

by C20203030 @ 2020-12-03 09:02:58

@gxy001 maybe

by Froggy @ 2020-12-25 07:22:38

确实有锅，但复杂度是对的。

还有我是菜鸡不是神蛙。