社区讨论

关于一种点分治找重心写法的疑问

MMinecraft万岁
P4292[WC2010] 重建计划参与者 2已保存回复 3

讨论操作

快速查看讨论及其快照的属性，并进行相关操作。

当前回复
3 条
当前快照
1 份
快照标识符
@lo3exfrh
此快照首次捕获于
2023/10/24 05:31
2 年前
此快照最后确认于
2023/10/24 05:31
2 年前
查看原帖
RT\text{RT}
我是对照 Zcus 大佬在 点分治模板 的代码学的。
CPP
inline void getroot(int x,int fa,int rt){
    mxsz[x]=0;
    for(int i=head[x];i;i=e[i].nxt){
        int v=e[i].to;
        if(v==fa||del[v]) continue;
        mxsz[x]=mx(mxsz[x],sz[v]);
        getroot(v,x,rt);
    }

    mxsz[x]=mx(mxsz[x],sz[rt]-sz[x]);
    if(mxsz[x]<mxsz[mnp]) mnp=x;

    return ;
}
这种写法我开始让 mnp=xmnp=x ，调用 getroot(x,0,x) 的时候开始的几个比较全部在和 mxsz[x]mxsz[x] 比较，但是这时候的 mxsz[x]mxsz[x] 显然没有处理完毕。 可不可能造成某个 mxsz[v]mxsz[v] 其实是小的，但是因为先和没有处理完的较小的 mnsz[x]mnsz[x] 比较导致算法假了阿？
理论上说是这样，但是我发现这样跑跑的还挺快的。 在 P4292 里面用上面的写法能过，但是如果用下面的写法会  #5 TLE\text{ \#5 TLE}
CPP
inline void getroot(int x,int fa,int rt){
    mxsz[x]=0;
    for(int i=head[x];i;i=e[i].nxt){
        int v=e[i].to;
        if(v==fa||del[v]) continue;
        mxsz[x]=mx(mxsz[x],sz[v]);
    }

    mxsz[x]=mx(mxsz[x],sz[rt]-sz[x]);//保证一定在比较前先处理完
    if(mxsz[x]<mxsz[mnp]) mnp=x;

    for(int i=head[x];i;i=e[i].nxt){
        int v=e[i].to;
        if(v==fa||del[v]) continue;
        getroot(v,x,rt);
    }
    return ;
}
不是很懂，有没有大佬能解释一下。

回复

共 3 条回复，欢迎继续交流。

正在加载回复...