关于点分治的size数组

P3806 【模板】点分治 1

ningago @ 2022-06-07 17:48:49

RT。请看下面代码的注释部分:

void solve(int k)
{
    vis[k] = 1;
    calc(k);
    for(int i = h[k];~i;i = ne[i])
    {
        int nx = e[i];
        if(vis[nx])
            continue;
        root = 0;
        get_root(nx,0,sz[nx]);//"3"
        solve(root);
    }
}

int main()
{
    memset(h,-1,sizeof(h));
    scanf("%d%d",&n,&m);
    for(int i = 1,x,y,z;i < n;i++)
    {
        scanf("%d%d%d",&x,&y,&z);
        add(x,y,z);
    }
    for(int i = 1;i <= m;i++)
        scanf("%d",&q[i]);
    maxp[0] = n;
    get_root(1,0,n);//"1"
    get_root(root,0,n);//"2"
    solve(root);
    for(int i = 1;i <= m;i++)
        printf("%s\n",ok[i] ? "AYE" : "NAY");
    return 0;
}

在许多的题解中 "2" 这行是不需要加的。但根据Agoh大佬在B站的说法,"1"中算出的sz是以节点 1 为根的子树大小,会影响"3"带来的复杂度,所以加上"2"算出"sz"的就是以 root 为根的大小。

然后……运行时间还多了5ms……

所以有没有必要加上"2"呢?


by gxy001 @ 2022-06-07 18:01:55

@ningago http://liu-cheng-ao.blog.uoj.ac/blog/2969


by liqingyang @ 2022-06-07 18:02:01

不加时间复杂度好像也是对的,但是加的时间复杂度对得一目了然


by ningago @ 2022-06-07 18:05:23

@gxy001

谢谢orz


by ningago @ 2022-06-07 18:06:12

@liqingyang

所以要卡起常来我是加还是不加呢


by Alex_Wei @ 2022-06-07 18:13:24

@ningago 不加的话时间复杂度没问题,但是递归深度没有严格 \log n 保证,应该不会超过 2\log n,但可以构造数据卡成大于 \log n

当需要用到点分树的性质来构造的时候必须规范写法,否则就寄了,举个例子:https://www.luogu.com.cn/problem/CF776F


by Alex_Wei @ 2022-06-07 18:14:12

至于常数的话,其实不好说,因为每次重新 dfs 求 size 也挺慢的。


by Alex_Wei @ 2022-06-07 18:14:51

(顺便提供一道水黑,大雾)


by ningago @ 2022-06-07 18:16:47

@Alex_Wei

thx orz


|