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 点分治递归的时候找重心是为了让递归层数不超过
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