BZOJ 3879 SvT：後綴樹 + 虛樹求 LCP 之和

題目大意

給定一字串，多組查詢，每組給出若干後綴索引，求這些後綴兩兩之間的最長公共前綴 (LCP) 長度之和。資料保證總查詢後綴數 Σ|ask| = O(n)。

核心思路：虛樹優化

後綴樹上，任意兩後綴的 LCP 對應其最近公共祖先 (LCA) 的字串深度。若直接對每組查詢兩兩計算 LCA，複雜度過高。觀察到查詢點集總大小為 O(n)，可構建虛樹：

1. 將查詢點按 DFS 序排序。
2. 插入必要的 LCA 節點，構成一棵只包含查詢點及其 LCA 的樹。
3. 在虛樹上做樹形 DP，累加每條邊的貢獻：size[u] * (size[u] - 1) / 2 * (len[u] - len[parent])，其中 size[u] 為子樹內查詢點數。

關鍵技術細節

後綴自動機 (SAM) 建樹

反向插入字元，建立 SAM。每個狀態對應一個等價類，len 為最長長度，link 為後綴鏈結。SAM 的父樹即為後綴樹的壓縮版。

LCA 倍增預處理

在 SAM 父樹上 DFS 記錄 dfn (時間戳)、deep、fa[u][k]，支援 O(log n) LCA 查詢。

虛樹構建 (單調棧)

sort(src+1, src+num+1, cmp); // 按 dfn 排序
stack[++top] = src[1];
for i = 2..num:
    lca = LCA(stack[top], src[i]);
    while deep[stack[top]] > deep[lca]:
        if deep[stack[top-1]] <= deep[lca]:
            add_edge(lca, stack[top]);
        top--;
    if stack[top] != lca:
        add_edge(stack[top], lca);
        stack[++top] = lca;
    stack[++top] = src[i];
// 最後連接棧內剩餘邊

時間戳優化

多組查詢共用陣列時，用 T (查詢編號) 標記節點是否屬於當前查詢，避免每次 memset 清空，將清理複雜度從 O(n) 降為 O(查詢點數)。

複雜度分析

• SAM 建構：O(n)
• LCA 預處理：O(n log n)
• 單組查詢：O(|ask| log |ask|) (排序 + 虛樹構建 + DP)
• 總計：O(n log n + Σ|ask| log |ask|) = O(n log n)

完整代碼架構

代碼包含：SAM 結構體、邊表 (靜態陣列)、DFS、倍增 LCA、虛樹命名空間 (隔離多查詢狀態)、主流程。注意陣列大小開 MAX = 1e6+10，避免爆記憶體。