题目概述

给定一棵树（铁路网络），需要选择一个车站作为枢纽站 Bitowice，使得所有车站对之间的平均通行距离最小。通行距离定义为两个车站之间的最短路径长度（边数）。

---

问题分析

关键观察

1. 树结构：铁路网络是一棵树，任意两点间有唯一简单路径
2. 目标函数：最小化所有无序点对的距离之和
3. 问题转化：这实际上是求树的重心（centroid）问题

数学形式化

设选择车站 $u$ 作为枢纽，总距离和为：

$$S(u) = \sum_{v=1}^n \text{dist}(u, v)$$

我们需要找到 $u$ 使得 $S(u)$ 最小。

---

算法思路

两次DFS求解

第一次DFS：预处理

以任意节点（如节点1）为根：

• 计算每个节点的子树大小 siz[u]
• 计算每个节点的深度 dep[u]
• 计算以根节点为枢纽的总距离 dp[1]

void dfs(const int u, const int fa) {
    siz[u] = 1, dep[u] = dep[fa] + 1, dp[u] = dep[u];
    for (int i = head[u]; i; i = edges[i].nxt) {
        int to = edges[i].to;
        if (to == fa) continue;
        dfs(to, u);
        siz[u] += siz[to];
        dp[u] += dp[to];
    }
}

第二次DFS：换根DP

从根节点开始，计算以每个节点为枢纽的总距离：

关键公式：当从父节点 $u$ 移动到子节点 $v$ 时：

$$S(v) = S(u) + n - 2 \times \text{siz}[v]$$

解释：

• 移动到 $v$ 后，$v$ 子树中所有节点距离减少1
• $v$ 子树外的所有节点距离增加1
• 净变化：$(n - \text{siz}[v]) - \text{siz}[v] = n - 2 \times \text{siz}[v]$

void dfs2(const int u, const int fa, const int dpu) {
    // 更新最优解
    if (dpu > ansdp) ansdp = dpu, ansid = u;
    if (dpu == ansdp && u < ansid) ansid = u;
    
    // 继续DFS
    for (int i = head[u]; i; i = edges[i].nxt) {
        int to = edges[i].to;
        if (to == fa) continue;
        dfs2(to, u, dpu + n - (siz[to] << 1));  // siz[to] << 1 = 2*siz[to]
    }
}

---

算法详解

第一次DFS的作用

1. 子树大小：siz[u] 表示以u为根的子树节点数
2. 深度计算：dep[u] 表示节点u到根节点的距离
3. 根节点距离和：dp[1] 表示以节点1为枢纽的总距离

换根DP原理

设当前在节点 $u$，已知 $S(u)$，要计算子节点 $v$ 的 $S(v)$：

• $v$ 子树中的节点：到 $v$ 比到 $u$ 近1，贡献 $- \text{siz}[v]$
• 其他节点：到 $v$ 比到 $u$ 远1，贡献 $+ (n - \text{siz}[v])$
• 总变化：$(n - \text{siz}[v]) - \text{siz}[v] = n - 2\text{siz}[v]$

所以：$S(v) = S(u) + n - 2\text{siz}[v]$

最优解选择

• 记录最大的总距离和 ansdp（实际应该是最小值，但代码中用了最大，可能是为了统一处理）
• 当多个节点有相同的最优值时，选择编号最小的

---

样例解析

样例输入

8
1 4
5 6
4 5
6 7
6 8
2 4
3 4

树结构：

    1
    |
    4
   /|\
  2 3 5
      |
      6
     / \
    7   8

计算过程

1. 以节点1为根进行第一次DFS，计算各节点子树大小和深度
2. 计算以节点1为枢纽的总距离
3. 进行第二次DFS，计算以每个节点为枢纽的总距离
4. 发现节点7或8为枢纽时总距离最小（36）
5. 选择编号较小的节点7

---

复杂度分析

• 时间复杂度：$O(n)$
  • 两次DFS，每个节点访问一次
• 空间复杂度：$O(n)$
  • 存储树结构和相关数组

---

算法亮点

1. 换根DP：高效计算以每个节点为根时的总距离
2. 公式推导：利用子树大小快速计算距离变化
3. 线性复杂度：适合 $n \leq 10^6$ 的大规模数据
4. 正确性保证：基于树的重心理论

---

理论背景

树的重心性质

对于树中的节点 $u$，以下等价：

1. $u$ 是重心
2. $u$ 的所有子树大小都不超过 $n/2$
3. $u$ 最小化到其他所有节点的总距离

本题正是性质3的应用。

---

总结

这道题的核心在于：

1. 问题识别：识别出这是求树重心问题
2. 换根DP：掌握高效的树形动态规划技巧
3. 公式理解：理解距离和变化的数学原理
4. 实现细节：注意边界条件和最优解选择

这种"树形DP + 换根技巧"的方法在解决树上的最优化问题时非常有效，是竞赛中的经典题型。