LG 4299 首都

zcmimi at 
查看原题'" class='mdui-btn mdui-btn-raised'>点击加载点击跳转 LCT 维护重心这里利用了两个重心性质:树中所有点到某个点的距离和中,到重心的距离和是最小的,如果有两个距离和,他们的距离和一样。把两棵树通过某一点相连得到一颗新的树,新的树的重心必然在连接原来两棵树重心的路径上。我们需要维护子树的大小合并的时候连接两棵树,分离出连接原来两棵树重心的路径,在链上搜索出答案方法类似平衡树的查找……