关于点分治的一点疑惑
查看原帖
关于点分治的一点疑惑
333580
Zwaire楼主2022/1/17 11:09

有关在点分治找重心的过程中,子节点的大小我设的是 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的初始值不同

2022/1/17 11:09
加载中...