HEOI 2014 大工程：虛樹 + 樹形 DP 統計關鍵點距離極值

問題背景

樹上多次查詢，每次給定關鍵點集合，求：最大距離、最小距離、距離和。構建虛樹將關鍵點及其 LCA 連接，在虛樹上 DP。

虛樹構建

1. 關鍵點按 DFS 序排序
2. 棧維護當前鏈，插入 LCA 連接
3. 邊權為原樹上兩點距離

DP 狀態定義

• mxdis[u]：u 子樹內關鍵點到 u 最大距離
• mndis[u]：u 子樹內關鍵點到 u 最小距離
• mx[u]：u 子樹內任意兩關鍵點最大距離
• mn[u]：u 子樹內任意兩關鍵點最小距離
• sum[u]：u 子樹關鍵點到 u 距離和
• cnt[u]：u 子樹關鍵點個數

轉移方程

對每個子 v，邊長 w：

mxdis[u] = max(mxdis[u], mxdis[v] + w)
mndis[u] = min(mndis[u], mndis[v] + w)
mx[u] = max(mx[u], mx[v], mxdis[u] + mxdis[v] + w)  // 合併兩子樹最遠
mn[u] = min(mn[u], mn[v], mndis[u] + mndis[v] + w)  // 合併兩子樹最近
sum[u] += sum[v] + cnt[v] * w
cnt[u] += cnt[v]

時間戳優化

用 tim[u] 標記當前查詢的關鍵點，避免每次清空數組，O(1) 重置。

複雜度

預處理 LCA O(n log n)，單次查詢 O(k log k)（k 為關鍵點數），虛樹節點 ≤ 2k，DP 線性。總體極優。