menu zcmimi's blog

arrow_back 树的重心

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

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

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

每次都选树的重心来处理,最多需要处理$\log n

zc
2020-01-18 22:40

```cpp

include<bits/stdc++.h>

namespace ZDY{

#pragma GCC optimize(3)
#define il __inline__ __attr
zc
2019-12-21 19:47
1 / 1
Search
search