大家都是这样写的 但这里感觉不严谨？

P3806 【模板】点分治 1

ZhuMingYang @ 2022-07-28 10:22:25

void solve(int x)
{
    vis[x]=1;
    calc(x);
    for(int i=head[x];i;i=edge[i].nxt)
    {
        int y=edge[i].to;
        if(vis[y]) continue;
        rt=0,sum=sz[y],mn=n;//这里子树不一定大小是sz[y]
        getrt(y,x);
        solve(rt);
    }
}

之前getrt()并不是随root搜下去的，这里的y可能是x的父亲，所以sz[y]并不一定是y子树的大小

by BlankAo @ 2022-07-28 10:23:56

虽然是非良定义的，但是时间复杂度是可以证明为正确的https://liu-cheng-ao.blog.uoj.ac/blog/2969

by Register_int @ 2022-07-28 10:36:30

@ZhuMingYang 这不是打着标记吗？不可能搜回去啊

by 7KByte @ 2022-07-28 10:37:27

我的写法是 solve(x, csz)，把对应 x 连通块的大小作为参数传下去。

by ZhuMingYang @ 2022-07-28 10:40:22

@Register_int 不是搜回去 你看看上面BlankAo发的那个blog就知道我在问啥了

by hy233 @ 2022-07-28 10:42:47

@BlankAo 虽然复杂度是对的，但是常数巨大，在另一道板题P4149貌似过不了

by hy233 @ 2022-07-28 10:44:15

@hy233 可以getrt(y,x)后再getrt(rt,0)一遍，将siz更新。

by ZhuMingYang @ 2022-07-28 10:46:32

@hy233 谁说过不了的

https://www.luogu.com.cn/record/24853162

by hy233 @ 2022-07-28 10:47:50

@ZhuMingYang \jk

那是我人傻常数大

你也可以看我的提交记录

我刚刚还试了一下，改一下就过了

by ZhuMingYang @ 2022-07-28 11:00:24

@hy233 我改后还没改前快

|