问题分析

本题要求k名特工在树上访问所有n个城市，每天只能有一个特工移动，每个城市只能被一个特工访问。目标是求最少天数。

关键洞察

1. 问题转化

将树划分为k个连通区域，每个区域包含一个特工的初始位置。特工只需访问自己区域内的所有节点。

2. 步数计算

对于包含m个节点的连通块，特工从起点s出发访问所有节点所需的最小步数为：

• 需要遍历所有m-1条边
• 最优策略是最后停留在离起点最远的点
• 步数 = 2×(m-1) - d，其中d是起点到连通块内最远点的距离

3. 总天数公式

总天数 = Σ[2×(m_i-1) - d_i] = 2×(n-k) - Σd_i

其中：

• m_i是第i个连通块的节点数
• d_i是第i个起点到其连通块内最远点的距离

核心思想

最小化总天数等价于最大化Σd_i

解决方案

算法步骤

1. Voronoi划分：以k个起点为中心，将树划分为k个区域，每个节点属于离它最近的起点

2. 计算最远距离：对于每个Voronoi区域，计算起点到区域内最远点的距离d_i

3. 结果计算：总天数 = 2×(n-k) - Σd_i

技术细节

• Voronoi划分：使用多源BFS，每个节点分配给距离最近的起点
• 最远距离计算：通过两次DFS（树形DP）计算：
  • 第一次DFS：计算每个节点到子树内最远点的距离
  • 第二次DFS：计算每个节点到整棵树最远点的距离

算法复杂度

• 时间复杂度：O(n)
• 空间复杂度：O(n)

样例验证

样例1

输入：
6 2
2 6
1-2, 2-3, 2-4, 4-5, 5-6

划分：
- 特工1：城市1,2,3,4，最远距离2
- 特工2：城市5,6，最远距离1

计算：2×(6-2) - (2+1) = 8-3 = 5

样例2（链状结构）

n=500000，特工在1和n
答案：499998

样例3（星状结构）

n=500000，特工在1
答案：999997

正确性证明

1. Voronoi划分最优性：每个节点分配给最近起点是最自然的划分方式
2. 步数公式正确性：基于树遍历的最优策略推导
3. 算法效率：线性复杂度处理大规模数据

优化要点

• 使用邻接表存储树结构
• 避免递归过深，可使用迭代DFS
• 注意整数溢出，使用long long

该解决方案能够高效处理题目给出的所有数据范围，包括n=500000的最大测试用例。