樹上任意兩點距離之和：O(n) 複雜度的 DFS 解法詳解

給定一棵無根樹，節點編號 1 到 n，邊長均為 1。要求計算任意兩點之間的距離之和（即每個點到其他所有點距離之和），時間複雜度必須為 O(n)。這是一道經典的樹形 DP / 換根 DP 題目，核心思想是利用「換根」技巧在線性時間內求出所有節點的答案。

核心思路：兩遍 DFS 實現換根 DP

1. 第一遍 DFS（自底向上）：任選一個節點為根（如 1 號），計算每個節點的子樹大小 sz[u] 和該節點到其子樹內所有節點的距離之和 dp[u]。同時可得根節點 1 的答案 ans[1] = dp[1]。
2. 第二遍 DFS（自頂向下，換根）：已知父節點 u 的答案 ans[u]，可在 O(1) 時間內推導出子節點 v 的答案 ans[v]。

   推導公式：ans[v] = ans[u] + (n - 2 * sz[v])。

   原理：從 u 移動到 v，v 的子樹內 sz[v] 個節點距離各減 1，其餘 n - sz[v] 個節點距離各加 1。總變化量 = (n - sz[v]) - sz[v] = n - 2*sz[v]。

關鍵點總結

• 無根樹任選根節點不影響結果。
• 第一遍 DFS 求子樹大小與根節點答案。
• 第二遍 DFS 利用換根公式 O(1) 推導所有節點答案，總複雜度 O(n)。
• 邊長為 1 簡化了距離計算，若邊有權重，公式相應調整為權重值。

掌握換根 DP 模板，即可輕松解決「樹上所有節點到其他節點距離之和」「樹的重心」「樹的直徑」等一系列經典問題。