$\text{RT}$

我是对照 Zcus 大佬在 点分治模板 的代码学的。

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=x$ ，调用 getroot(x,0,x) 的时候开始的几个比较全部在和 $mxsz[x]$ 比较，但是这时候的 $mxsz[x]$ 显然没有处理完毕。 可不可能造成某个 $mxsz[v]$ 其实是小的，但是因为先和没有处理完的较小的 $mnsz[x]$ 比较导致算法假了阿？

理论上说是这样，但是我发现这样跑跑的还挺快的。 在 P4292 里面用上面的写法能过，但是如果用下面的写法会 $\text{ \#5 TLE}$

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 ;
}

不是很懂，有没有大佬能解释一下。