点分治

概述

点分治适合处理大规模的树上路径信息问题。

点分治的实现基于以下结论：一棵子树上的任意一条路径，要么经过树根，要么被完全包含在树根的一棵子树中。

定义 $solve()$ 函数，对每棵子树进行分值处理，并保证 $O(n\log n)$ 的时间复杂度。

题目链接

给定一棵有 $n$ 个节点的树，边权为 $1$ 。共有 $q$ 次询问，每次给出 $k$ 个节点，求： $k$ 个节点间两两距离之总和；最短距离；最长距离。

$1\le n \le 1000000,1 \le q \le 1000000, \Sigma{k}\le 2 * n$

感谢@tth37 的贡献