【Codeforces 768G】The Winds of Winter
线段树合并
题目大意：
给定一棵有根树，去掉一个点及与其相关的边后，会变成一棵森林。
删掉结点后，可以选择一个结点，断掉其与父亲的连边，并连到另一个结点上。不能改变森林的树的个数。最多操作一次。
要使得森林中最大的树的大小最小。
对删掉每个结点，求森林中最大的树的大小最小是多少。询问互相独立。
题解：
对删掉每个点后，显然是删最大的树里的子树，接在最小的树上。
删掉每个结点后的最大、次大、最小子树都可以处理出来。
令最大、最小子树的大小分别为 $mx,mn$，显然让它们尽可能接近是最好的。
令 $mid=\lfloor\frac{mx+mn}{2}\rfloor$，这是我们要删到的目标状态。
我们要在最大的那棵树中删除 $k$。那么当 $mn+k\leq mid$ 时令 $k$ 尽可能大，当 $mn+k> mid$ 时令 $k$ 尽可能小。
我们在这棵子树中找满足条件的最优的 $k$ 即可，然后取较优答案。注意答案至少是次大的子树大小，要和它取 $\max$。
那么我们需要实现在一棵子树中，查找大小在 $l\sim r$ 之间的最大、最小子树大小。
由于是有根树，所以其儿子所在子树的信息，可以通过线段树合并统计，然后在线段树上二分即可查询。
考虑如何统计每个点父亲所在信息。
设当前结点的子树大小为 $sz$，发现这个点到根路径上的子树大小都减少了 $sz$。
还有就是，以当前结点为根的这棵子树都没有了。
那我们分两部分查询：1. 整棵树去掉到根路径去掉当前子树。2. 到根路径。
对于第一种情况，我们用线段树维护到根路径所有点的子树大小信息，还有通过线段树合并得到的当前子树的信息和整棵树的信息。这些信息是可以直接在线段树上做差的。在三棵树上一起二分即可。
对于第二种情况，我们维护了到根路径的信息，然后相当于是需要进行全局减某个数以后再进行查询。这个可以把查询的范围 $l,r$ 都加上 $sz$ 后查询，然后查询的结果再减去 $sz$ 就好了。
时间复杂度 $O(n\log n)$，空间复杂度 $O(n\log n)$。
这里对线段树合并进行可持久化一下比较好处理。
一开始以为可持久化线段树合并的空间复杂度是两个 $\log$ 的，实际上只多了一倍常数。
Code：
#include<iostream>
#include<algorithm>
using namespace std;
const int inf=0x3fffffff;
const int N=1e5+5;
int n,rt,head[N],sz[N],fa[N],ans[N],deg[N],cnt,sr;
struct info{
int mx1,id1,mx2,id2,mn,idn;
inline void update(int id,int sz){
if(sz<mn||mn==0)mn=sz,idn=id;
if(sz>mx1){
mx2=mx1,id2=id1;
mx1=sz,id1=id;
}else
if(sz>mx2){
mx2=sz,id2=id;
}
}
}f[N];
struct edge{
int to,nxt;
}e[N<<1];
namespace sgt{
const int M=N*380;
int rt[N];
int ls[M],rs[M],sz[M],nod;
void add(int&o,int l,int r,const int&pos){
if(!o)o=++nod;
if(l==r)++sz[o];else{
const int mid=l+r>>1;
if(pos<=mid)add(ls[o],l,mid,pos);else add(rs[o],mid+1,r,pos);
sz[o]=sz[ls[o]]+sz[rs[o]];
}
}
void del(int&o,int l,int r,const int&pos){
if(l==r)--sz[o];else{
const int mid=l+r>>1;
if(pos<=mid)del(ls[o],l,mid,pos);else del(rs[o],mid+1,r,pos);
sz[o]=sz[ls[o]]+sz[rs[o]];
}
}
int merge(int ld,int rd,int l,int r){
if(!ld||!rd)return ld|rd;
int id=++nod;
if(l==r){
sz[id]=sz[ld]+sz[rd];
return id;
}
const int mid=l+r>>1;
ls[id]=merge(ls[ld],ls[rd],l,mid);
rs[id]=merge(rs[ld],rs[rd],mid+1,r);
sz[id]=sz[ls[id]]+sz[rs[id]];
return id;
}
int query_min(int rd,int ld,int ld_,int l,int r,const int&L,const int&R){
if(sz[rd]<=sz[ld]+sz[ld_]||L>R)return inf;
if(l==r)return l;
const int mid=l+r>>1;
int ret=inf;
if(L<=mid)ret=query_min(ls[rd],ls[ld],ls[ld_],l,mid,L,R);
if(ret!=inf)return ret;
if(mid<R)ret=query_min(rs[rd],rs[ld],rs[ld_],mid+1,r,L,R);
return ret;
}
int query_max(int rd,int ld,int ld_,int l,int r,const int&L,const int&R){
if(sz[rd]<=sz[ld]+sz[ld_]||L>R)return 0;
if(l==r)return l;
const int mid=l+r>>1;
int ret=0;
if(mid<R)ret=query_max(rs[rd],rs[ld],rs[ld_],mid+1,r,L,R);
if(ret!=0)return ret;
if(L<=mid)ret=query_max(ls[rd],ls[ld],ls[ld_],l,mid,L,R);
return ret;
}
}
void dfs(int now,int pre){
sz[now]=1;
for(int i=head[now];i;i=e[i].nxt)
if(e[i].to!=pre){
fa[e[i].to]=now;
dfs(e[i].to,now);
sz[now]+=sz[e[i].to];
f[now].update(e[i].to,sz[e[i].to]);
}
if(now!=rt)f[now].update(fa[now],n-sz[now]);
sgt::add(sgt::rt[now],1,n,sz[now]);
for(int i=head[now];i;i=e[i].nxt)
if(e[i].to!=pre)
sgt::rt[now]=sgt::merge(sgt::rt[now],sgt::rt[e[i].to],1,n);
}
int query_min(int l,int r,int nw,int qrt){
if(l>r)return 0x3fffffff;
if(fa[nw]!=qrt)
return sgt::query_min(sgt::rt[qrt],0,0,1,n,l,r);
return min(sgt::query_min(sgt::rt[rt],sgt::rt[nw],sr,1,n,l,r),
sgt::query_min(sr,0,0,1,n,min(l+sz[nw],n+1),min(r+sz[nw],n))-sz[nw]);
}
int query_max(int l,int r,int nw,int qrt){
if(l>r)return 0;
if(fa[nw]!=qrt)
return sgt::query_max(sgt::rt[qrt],0,0,1,n,l,r);
return max(sgt::query_max(sgt::rt[rt],sgt::rt[nw],sr,1,n,l,r),
sgt::query_max(sr,0,0,1,n,min(l+sz[nw],n+1),min(r+sz[nw],n))-sz[nw]);
}
void getans(int num){
if(deg[num]==1)ans[num]=n-1;else{
const int mid=f[num].mn+f[num].mx1>>1;
int mn=query_max(1,mid-f[num].mn,num,f[num].id1);
int mx=query_min(mid+1-f[num].mn,f[num].mx1-1,num,f[num].id1);
int s=f[num].mx1;
if(mn>0)s=min(s,max(f[num].mx1-mn,f[num].mx2));
if(mx<f[num].mx1)s=min(s,max(f[num].mn+mx,f[num].mx2));
ans[num]=s;
}
}
void get(int now,int pre){
getans(now);
sgt::add(sr,1,n,sz[now]);
for(int i=head[now];i;i=e[i].nxt)
if(e[i].to!=pre)
get(e[i].to,now);
sgt::del(sr,1,n,sz[now]);
}
int main(){
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
cin>>n;
for(int i=1;i<=n;++i){
int u,v;
cin>>u>>v;
if(!u||!v)rt=u|v;else{
e[++cnt]=(edge){v,head[u]},head[u]=cnt;
e[++cnt]=(edge){u,head[v]},head[v]=cnt;
++deg[u],++deg[v];
}
}
dfs(rt,0);
getans(rt);
for(int i=head[rt];i;i=e[i].nxt)
get(e[i].to,rt);
for(int i=1;i<=n;++i)
cout<<ans[i]<<'\n';
return 0;
}