木構造の分割処理

基本概念

1. 木の分割処理：木構造を複数の非交差チェーンに分割する手法で、主に重み付きチェーン分割を用いる。以下の操作をサポート：

   • ノードxからノードyまでの最短経路上の全ノードの値の更新
   • ノードxからノードyまでの最短経路上の全ノード値の合計取得
   • ノードxとその部分木の値の更新
   • ノードxとその部分木の値の合計取得

2. 重み付き子ノード：ノードuの子ノードの中で部分木サイズが最大のノード

3. 軽量子ノード：重み付き子ノード以外の子ノード

4. 重み付き辺：ノードuとその重み付き子ノードを結ぶ辺

5. 軽量辺：ノードuとその軽量子ノードを結ぶ辺

6. 重み付きチェーン：重み付き辺で構成されるパス

7. 軽量チェーン：軽量辺で構成されるパス

重要な性質：

• 1つの木に複数の重み付き/軽量チェーンが存在可能
• 軽量子ノードも自身の重み付き子ノードを持つ
• 子ノードを持つノードは必ず1つの重み付き子ノードを持つ
• 葉ノードは重み付き子ノードを持たない
• 各重み付きチェーンの先頭は軽量子ノード
• 軽量子ノードは長さ1の重み付きチェーンとみなせる
• 処理は2つのノードが交互に上昇する形で進行
• 根から葉までの軽量辺数と重み付きチェーン数は各々O(logn)以下

実装手法

主要コンポーネント

木の分割処理はDFS順序とセグメント木で実現。ノードuとその部分木はDFS順序で連続する性質を利用。

処理は3部構成：

1. dfs1関数：

   • 各ノードの親ノード(fa)
   • 深さ(dep)
   • 部分木サイズ(size)
   • 重み付き子ノード(son) を事前計算

2. dfs2関数：

   • DFS順序(id)
   • 順序からノードへのマッピング(rk)
   • 各ノードのチェーン先頭(top) を事前計算 ※重み付き子ノードを優先的に探索し、重み付きチェーンがDFS順序で連続するよう処理

3. セグメント木： DFS順序における重み付きチェーンと部分木の値管理

操作処理

経路更新

LCA計算と同様のアプローチ。異なるチェーンに属する場合、チェーン先頭の深さが大きい方から処理：

void 経路更新(int x, int y, int z) {
    while(top[x] != top[y]) {
        if(dep[top[x]] < dep[top[y]]) swap(x,y);
        セグ木更新(1, id[top[x]], id[x], z);
        x = fa[top[x]];
    }
    if(dep[x] > dep[y]) swap(x,y);
    セグ木更新(1, id[x], id[y], z);
}

時間計算量: O(log²n)

経路クエリ

更新処理と同様の手法で合計値を計算：

int 経路クエリ(int x, int y) {
    int 合計 = 0;
    while(top[x] != top[y]) {
        if(dep[top[x]] < dep[top[y]]) swap(x,y);
        合計 = (合計 + セグ木クエリ(1, id[top[x]], id[x])) % p;
        x = fa[top[x]];
    }
    if(dep[x] > dep[y]) swap(x,y);
    合計 = (合計 + セグ木クエリ(1, id[x], id[y])) % p;
    return 合計;
}

時間計算量: O(log²n)

部分木更新

DFS順序で連続する性質を利用：

void 部分木更新(int x, int z) {
    セグ木更新(1, id[x], id[x]+size[x]-1, z);
}

時間計算量: O(logn)

部分木クエリ

同様にDFS順序範囲でクエリ：

int 部分木クエリ(int x) {
    return セグ木クエリ(1, id[x], id[x]+size[x]-1);
}

時間計算量: O(logn)

応用例

LCA計算

チェーン分割を利用した効率的なLCA計算：

int LCA(int x, int y) {
    while(top[x] != top[y]) {
        if(dep[top[x]] <= dep[top[y]]) swap(x,y);
        x = fa[top[x]];
    }
    return dep[x] < dep[y] ? x : y;
}

辺重み管理

辺の重みを管理する応用：

int 最大辺重み(int x, int y) {
    int 最大値 = 0;
    while(top[x] != top[y]) {
        if(dep[top[x]] < dep[top[y]]) swap(x,y);
        最大値 = max(最大値, セグ木クエリ(1, pos[top[x]], pos[x]));
        x = fa[top[x]];
    }
    if(dep[x] > dep[y]) swap(x,y);
    if(x != y) 最大値 = max(最大値, セグ木クエリ(1, pos[x]+1, pos[y]));
    return 最大値;
}