「简单题」CF768G The Winds of Winter
皎月半洒花
2020-05-28 20:31:51
怪的怪的,为啥没题解啊。
首先可以发现,这个操作是具有贪心性质的。必然是从 $x$ 分出的最大 size 连通块里找出一棵子树连接到最小的 size 的连通块里。那么最后答案就是
$$
\max\{size_p-\zeta,size_q+\zeta,size_o\}
$$
其中 $p$ 是最大的连通块, $q$ 是最小的连通块,$o$ 是次大连通块,$\zeta$ 是摘下来的子树。那么不难知道这个东西是凸的。那么就考虑去二分这个 $ans$ ,$check$ 的时候自然需要满足
$$
\begin{aligned}
size_p-\zeta&\leq ans\\
size_q+\zeta&\leq ans\\
size_o&\leq ans
\end{aligned}
$$
考虑最后一个是一个定值,于是可以直接设成二分的下界。观察前面两个,本质上就是在查周围分出去的连通块里是否存在一个大小合适的子树 $\zeta$。于是就变成了一个拿 `mulity-set` 维护 dsu on tree 的直观题目。
(如果你会 dsu on tree 下面一段可以不看)
维护起来有些麻烦。考虑按照 dfs 序分别维护自己子树内的、祖先链上的、祖先除了自己以外的那些子孙。后面两个可以不断边插边删来做,而自己子树内的则可以考虑由于信息重复率大,所以采用启发式分治(启发式合并)策略——结合轻重链剖分的理论,因为从根到每个点至多经过 $\log n$ 条轻边,所以考虑每个点都只向自己的轻祖先贡献。那么过程就是先分治轻儿子并且清空贡献,然后暴力重儿子,再将轻儿子合并到重儿子的信息里。通过聚合分析不难知道这样是 $O(n\log n)$ 的。这也就是 dsu on tree 的过程。
最后有点细节需要注意,大概就是什么特判 $p=q$ 之类的。
```cpp
/* - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - */
sint other ;
sint dads ;
sint s[N] ;
vint E[N] ;
int n ;
int rt ;
int sz[N] ;
int fa[N] ;
int mx[N] ;
int mn[N] ;
int smx[N] ;
int son[N] ;
int ans[N] ;
void dfs(int x, int dad){
fa[x] = dad ; sz[x] = 1 ;
for (auto k : E[x])
if (k != dad){
dfs(k, x) ;
sz[x] += sz[k] ;
if (!son[x]) son[x] = k ;
if (sz[son[x]] < sz[k]) son[x] = k ;
}
if (x != rt)
other.ins(sz[x]) ;
}
bool isrt(int x){
return (bool)(x == rt) ;
}
bool chk(int v, int x){
// cout << v << " " << x << " " << mx[x] << " " << mn[x] << " " << sz[x] << " " << son[x] << " " << s[x].size() << '\n' ;
if (mx[x] == sz[son[x]]){
auto t = s[x].lwb(mx[x] - v) ;
if (t != s[x].js() && *t <= v - mn[x]) return 1 ;
return 0 ;
}
else {
auto t = other.lwb(mx[x] - v) ;
if (t != other.js() && (*t) <= v - mn[x]) return 1 ;
auto pq = dads.lwb(mx[x] - v + sz[x]) ;
if (pq != dads.js() && (*pq) <= v - mn[x] + sz[x]) return 1 ;
return 0 ;
}
}//mn[x] + x <= ans -> x <= ans - mn[x]
void solve(int x){
// debug(x, ' ') ;
// debug(other.size(), ' ') ;
// debug(s[x].size(), ' ') ;
// debug(dads.size()) ;
if (!isrt(x)){
other.era(other.fd(sz[x])) ;
if (!isrt(fa[x])) dads.ins(sz[fa[x]]) ;
}
mn[x] = n - sz[x] ;
mx[x] = max(n - sz[x], sz[son[x]]) ;
smx[x] = min(n - sz[x], sz[son[x]]) ;
// debug(x, '*') ;
// debug(mn[x], '*') ;
// debug(mx[x], '*') ;
// debug(smx[x], '\n') ;// puts("")
for (auto k : E[x]){
if (k == fa[x]) continue ;
if (k == son[x]) continue ;
solve(k) ;
for (auto t : s[k]) other.ins(t) ;
}
if (son[x]){
solve(son[x]) ;
swap(s[x], s[son[x]]) ;
chkmin(mn[x], sz[son[x]]) ;
if (!mn[x]) mn[x] = sz[son[x]] ;
}
for (auto k : E[x]){
if (k == fa[x]) continue ;
if (k == son[x]) continue ;
chkmin(mn[x], sz[k]) ;
chkmax(smx[x], sz[k]) ;
for (auto t : s[k])
other.era(other.find(t)) ;
}
int l = smx[x], r = mx[x], mid ;
if (smx[x] == mx[x]) goto ycy ;
while (l <= r){
mid = (l + r) >> 1 ;
if (!chk(mid, x)) l = mid + 1 ;
else ans[x] = mid, r = mid - 1 ;
}
ycy : if (!ans[x]) ans[x] = mx[x] ;
for (auto k : E[x]){
if (k == fa[x]) continue ;
if (k == son[x]) continue ;
for (auto t : s[k]) s[x].ins(t) ;
}
if (!isrt(x) && !isrt(fa[x]))
dads.era(dads.fd(sz[fa[x]])) ;
s[x].ins(sz[x]) ;
// debug(x, ' ') ;
// debug(other.size(), ' ') ;
// debug(s[x].size(), ' ') ;
// debug(dads.size()) ;
}
void output(){
for (int k = 1 ; k <= n ; ++ k)
printf("%d\n", ans[k]) ; return ;
}
int main(){
cin >> n ; int x, y ;
for (int i = 1 ; i <= n ; ++ i){
x = qr(), y = qr() ;
if (!x || !y) rt = x + y ;
else E[x].p_b(y), E[y].p_b(x) ;
}
dfs(rt, 0) ;
// debug(son, 1, n) ;
// debug(sz, 1, n) ;
solve(rt) ;
output() ;
return 0 ;
}
```