题目大意

给定一棵 $n$ 个节点的树，对于每个 $j = 1, 2, \dots, n$，求当选择 $j$ 个节点作为参会者时，能够作为开会地点（使得所有参会者到该点的距离和最小）的候选点数量的最大值。

解题思路

关键观察

1. 候选点的性质：在树中，使得所有参会者距离和最小的点集构成一条路径，这条路径就是树的直径在参会者点集诱导子图上的对应。

2. 奇偶性分析：

   • 当 $j$ 为奇数时，答案总是 $1$，因为最优会议地点是唯一的中位数点
   • 当 $j$ 为偶数时，答案等于某条路径的长度加 $1$

3. 问题转化：对于偶数 $j$，我们需要找到包含 $j$ 个节点的连通子图，使得该子图的直径最大。

算法核心

1. 树链剖分：通过两次 DFS 预处理出父节点、深度、子树大小、重儿子、链顶等信息，用于快速计算 LCA 和距离。

2. 按最小子树大小分组：对于每个节点 $u$，计算 $x = n - \max(n - siz[u], siz[son[u]])$，这表示包含 $u$ 的最大连通块大小。

3. 直径维护：从大到小枚举连通块大小，动态维护当前所有节点的直径端点，利用树的直径性质：

   • 对于新加入的节点 $u$，检查是否能与当前直径端点 $x, y$ 形成更长的直径

复杂度分析

• 时间复杂度：$O(n \log n)$，主要来自树链剖分的 LCA 查询
• 空间复杂度：$O(n)$