传送门。
题意
有一棵树，可以断掉 \(2\) 条边，会形成三个连通块，求三个连通块中大小最大减最小的最小值。
分析
我们观察两条边之间的关系，分类考虑：
- 两条边成祖孙关系。
- 两条边没有祖孙关系。
首先，我们肯定我们的大方向，固一动一（说起来为什么想到了数学题），先固定一条边，再在其他边中取得最适合的边，那这一条边，我们显然可以确定，这条边应当是平分剩余的连通块。
对于第一种。
想出来了两种方法。
第一种，从上往下，先固定上面（令这个节点为 \(x\)），再在其下选边，如何选边，在子树中的所有节点中，选择子树中节点树最接近 \(\frac{siz_x}{2}\) 的点。使用 set 维护即可，至于如何快速维护子树的节点的节点数，可以使用树上启发式合并。
时间复杂度：\(O(n\log^2n)\)。
inline void dfs(int now,int fath) {
siz[now]=1,son[now]=0;
for(auto to:lj[now]) {
if(to==fath) continue;
dfs(to,now);
siz[now]+=siz[to];
if(siz[son[now]]<siz[to]) son[now]=to;
}
}
inline void add(int now,int fath,int x) {
se.insert(siz[now]);
for(auto to:lj[now]) if(to!=fath&&to!=x) add(to,now,0);
}
inline void redfs(int now,int fath,int opt) {
for(auto to:lj[now]) if(to!=fath&&to!=son[now]) redfs(to,now,0);
if(son[now]) redfs(son[now],now,1);
add(now,fath,son[now]);
int A=n-siz[now];
auto it=se.upper_bound(siz[now]/2);
if(it!=se.end()) MIN(A,*it);
if(it!=se.begin()) it--,MIN(A,*it);
if(it!=se.begin()) it--,MIN(A,*it);
if(!opt) se.clear();
}
第二种，从下往上，维护到父亲的链上的节点数，那此时，我们的节点数应当尽量接近 \(\frac{n-siz_{x}}{2}+siz_{x}\)。
inline void redfs(int now,int fath) {
int A=siz[now];
auto it=se.upper_bound((n-siz[now])/2+siz[now]);
if(it!=se.end()) MIN(A,(*it)-siz[now]);
if(it!=se.begin()) it--,MIN(A,(*it)-siz[now]);
if(it!=se.begin()) it--,MIN(A,(*it)-siz[now]);
se.insert(siz[now]);
for(auto to:lj[now]) if(to!=fath) redfs(to,now);
se.erase(se.find(siz[now]));
}
时间复杂度：\(O(n\log n)\)。
对于第二种。
我们只需要将我们跑完的节点加入 set 即可，最后尽量接近 \(\frac{n-siz_x}{2}\) 。
inline void reredfs(int now,int fath) {
int A=siz[now];
auto it=se.upper_bound((n-siz[now])/2);
if(it!=se.end()) MIN(A,*it);
if(it!=se.begin()) it--,MIN(A,*it);
if(it!=se.begin()) it--,MIN(A,*it);
for(auto to:lj[now]) if(to!=fath) reredfs(to,now);
se.insert(siz[now]);
}
于是就可以完美解决了。