关于点分治的一点疑惑

P3806 【模板】点分治 1

Zwaire @ 2022-01-17 11:09:47

有关在点分治找重心的过程中,子节点的大小我设的是 siz[y],但是很明显他的siz并不一定是我儿子节点的大小,但是并没有什么影响,这时我想找重心的过程貌似并不需要考虑。但是我让 siz[y] = n 时,发现 7 和 9 这两个点却 T 了,不明白这是为什么

正确的:

il void solve(int x)
{
    vis[x] = 1;
    judge[0] = 1; calc(x);
    for_edge(i, x)
    {
        int y = ver[i]; if(vis[y]) continue;
        sum = siz[y]; maxp[0] = INF; rt = 0;
        getweight(y, 0);
        solve(rt);
    }
}

T 掉的

il void solve(int x)
{
    vis[x] = 1;
    judge[0] = 1; calc(x);
    for_edge(i, x)
    {
        int y = ver[i]; if(vis[y]) continue;
        sum = n; maxp[0] = INF; rt = 0;
        getweight(y, 0);
        solve(rt);
    }
}

仅仅在sum的初始值不同


by Wuyanru @ 2022-01-17 11:15:09

@DRY—AYST 点分治递归的时候找重心是为了让递归层数不超过 \log n 层,确保时间复杂度,你的 sum 设成 n 的话大概率找到的点就不是重心,时间复杂度就炸了。


by Zwaire @ 2022-01-17 11:27:26

@初一吴彦儒 大概确实应该是这样,但是siz[y]不会被卡我就很疑惑


by RedreamMer @ 2022-01-17 11:39:28

其实第一种也能卡,但是这道题没卡,我记得有位老哥说过了


by Meatherm @ 2022-01-17 11:49:50

@RedreamMer 能卡了?/jk 我之前在 uoj 见过证明,说这也是对的


by Zwaire @ 2022-01-17 11:58:25

@Meatherm 能给个链接吗


by RedreamMer @ 2022-01-17 12:03:13

@Meatherm /jy 同求。


by Meatherm @ 2022-01-17 12:04:04

@DRY—AYST https://liu-cheng-ao.blog.uoj.ac/blog/2969


by Meatherm @ 2022-01-17 12:04:52

应该是这个吧。。错了别骂(x


|