zcmimi's blog

arrow_back树的重心共3篇文章

avatar
zc
2020-10-27 12:19:30

查看原题

点击跳转

既然对考虑每条边断开后产生的重心比较麻烦,那么换个方式:

考虑每个点成为重心的次数

首先找出重心作为树根

设当前节点为x,子树大小为siz_x,孩子的最大子树大小为g_x,割掉一条边后,另一棵树大小为S

考虑x不是重心的情况:

2(n-S-siz_x)\le n-S2g_x\le n-S

也就是

S\in [n-2siz_x,n-2g_x]

我们可以用树状数组维护并统计每个点割掉与父亲之间的边后形成的S

显然这条边不能在x的子树内,那么减去 进入x子树前后求和的差

考虑x为重心的情况:

ux重儿子,vx次重儿子

若割掉的边在u的子树中: 2siz_v\le n-S,即S\le n-2siz_v

否则: 2siz_u\le n-S,即S\le n-2siz_u

avatar
zc
2020-01-18 22:40:00
查看原题

点击跳转

先钦定树的重心处理出答案

若当前点是距离最大点对的lca(即在它们之间的路径上),这个点就是最优的

否则最优答案一定在最大点对的lca的子树中

每次都选树的重心来处理,最多需要处理\log n次,总复杂度\Theta(n \log n)

avatar
zc
2019-12-21 19:47:00
查看原题

点击跳转

1/1
Search
search