OI Problems   关于

分类

首先对情况进行分类：

情况一： 一条边在根节点到另一条边的路径上；

情况二： 任意一条边不在根节点到另一条边的路径上。

只需要按此分类计算答案即可。


代码实现

考虑用两个 multiset 分别维护当前点到根节点的路径上的点的子树大小以及不在当前点到根节点的路径上的遍历过的点的子树大小，对于每个点 uu，考虑选择其与其父亲相连的这条边作为其中一条断掉的边。

显然我们希望剩下两个连通块大小尽量接近，且它们的大小总和为 n−sun-s_u（其中 sus_u 为以 uu 为根的子树大小），那么只需找到一个大小最接近 12(n−su)\dfrac 12(n-s_u) 的部分即可。

特别的，对于情况一，因为要选择的边下的子树大小会包含点 uu 的子树，所以要找的大小应为最接近 12(n−su)+su\dfrac 12(n-s_u)+s_u 的那个。

而查找可以使用 multiset 自带的 lower_bound 实现，只需要检验其前面的一项和它本身一项即可。

时间复杂度 Θ(nlogn)\Theta(n\log n)。

  代码
// 2023.06.01

#include<bits/stdc++.h>
using namespace std;

int n,answer=0x7ffffff;
struct Edge{
    int to,nxt;
}edge[400001];
int head[200001],cntEdge;
void addEdge(int u,int v){
    edge[++cntEdge]={v,head[u]},head[u]=cntEdge;
}

int siz[200001];
void calcSize(int id,int father){
    siz[id]=1;
    for(int i=head[id];i;i=edge[i].nxt)
        if(edge[i].to!=father){
            calcSize(edge[i].to,id);
            siz[id]+=siz[edge[i].to];
        }
}

multiset<int> hissiz,othsiz;
// hissiz: 路径上的所有点的子树大小集合
// othsiz: 其它支路上的所有点的子树大小集合

void work(int id,int father){
    if(!hissiz.empty()){
        // 取路径上的另一条边
        auto tmp=hissiz.lower_bound(siz[id]+(n-siz[id])/2);
        if(tmp!=hissiz.end()){
            // 取比目标值大的第一个
            int x=siz[id],y=*tmp-siz[id],z=n-*tmp;
            answer=min(answer,max(x,max(y,z))-min(x,min(y,z)));
        }
        if(tmp!=hissiz.begin()){
            // 取比目标值小的第一个
            tmp--;
            int x=siz[id],y=*tmp-siz[id],z=n-*tmp;
            answer=min(answer,max(x,max(y,z))-min(x,min(y,z)));
        }
    }
    if(!othsiz.empty()){
        // 不取路径上的边
        auto tmp=othsiz.lower_bound((n-siz[id])/2);
        if(tmp!=othsiz.end()){
            // 取比目标值大的第一个
            int x=siz[id],y=*tmp,z=n-x-y;
            answer=min(answer,max(x,max(y,z))-min(x,min(y,z)));
        }
        if(tmp!=othsiz.begin()){
            // 取比目标值小的第一个
            tmp--;
            int x=siz[id],y=*tmp,z=n-x-y;
            answer=min(answer,max(x,max(y,z))-min(x,min(y,z)));
        }
    }
    if(id>1)hissiz.insert(siz[id]);
    for(int i=head[id];i;i=edge[i].nxt)
        if(edge[i].to!=father)
            work(edge[i].to,id);
    if(id>1)
        hissiz.erase(hissiz.find(siz[id])),
        othsiz.insert(siz[id]);
}

int main(){
    scanf("%d",&n);
    for(int i=1;i<n;i++){
        int u,v;
        scanf("%d%d",&u,&v);
        addEdge(u,v);
        addEdge(v,u);
    }
    calcSize(1,0);
    work(1,0);
    printf("%d\n",answer);
    return 0;
}