P4299 首都
容易发现,这个难啊,要动态维护重心,有一个 \(\color {black} {\text {n}} \color {red} {\text{aive}}\) 的想法就是直接 \(O (n \log^2 n)\) 启发式合并,但是我们的 \(\color {black} {\text {Y}} \color {red} {\text {outh518}}\) 大佬直接利用LCT爆切。
可以发现的是,如果两个树合并,那么他们的重心必定在原来两个树重心的路径上。那么我们其实可以合并后split一下利用splay来跳,可以快速得到重心的位置,这个复杂度可以做到 \(O(n \log n)\)。
/*
Name:
Author: Gensokyo_Alice
Date:
Description:
*/
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include