Day 047-Q5 | Link-Cut Tree 辺重みパスクエリ（辺ノードテクニック + 最大値伝播）

問題

$N$ 頂点の木（辺には重みあり）に対して以下の $Q$ クエリを処理せよ：

1 u v w：辺 $(u,v)$ の重みを $w$ に変更する
2 u v：頂点 $u$ から頂点 $v$ へのパス上の辺の重みの最大値を求めよ

制約

$2 \le N \le 2 \times 10^5$

$1 \le Q \le 2 \times 10^5$

$0 \le w \le 10^9$

時間制限: 3秒

入出力例

入力例 1

出力例 1

4
5
5

概念図: 辺ノードテクニックと Link-Cut Tree

ヒント（段階的開示）

ヒント1: 方向性

辺の重みを辺の端点のうち深さの深い方の頂点の値として持たせる（辺ノードテクニック）。これにより「辺重みのパス最大値」が「頂点値のパス最大値（辺ノードのみ非ゼロ）」と等価になり、Link-Cut Tree で処理できます。

ヒント2: アプローチ

辺 $(u,v,w)$ を辺ノード $e$（追加頂点）として $u-e-v$ の経路に変換し、$e$ の val を $w$ とする
頂点ノードの val = 0（辺ノードだけが非ゼロ）にすることで、path_max はパス上の辺重みの最大を返す
各ノードに mx（部分木内の最大 val）を保持し、push_up で集約
辺重み更新: 辺ノードの val を変更し、access で祖先の mx を更新

ヒント3: push_up と mx 集約

def push_up(self, x):
    l, r = self.ch[x]
    self.mx[x] = self.val[x]  # 自分の val
    if l: self.mx[x] = max(self.mx[x], self.mx[l])
    if r: self.mx[x] = max(self.mx[x], self.mx[r])

def path_max(self, x, y):
    self.make_root(x)
    self.access(y)
    return self.mx[y]  # x-y パスの Splay 木全体の mx

模範解答 (Python)

import sys
input = sys.stdin.readline

class LCT:
    def __init__(self, n):
        self.n = n
        self.ch = [[0, 0] for _ in range(n + 1)]
        self.par = [0] * (n + 1)
        self.val = [0] * (n + 1)
        self.mx = [0] * (n + 1)
        self.rev = [False] * (n + 1)

    def is_root(self, x):
        p = self.par[x]
        return p == 0 or (self.ch[p][0] != x and self.ch[p][1] != x)

    def push_up(self, x):
        l, r = self.ch[x]
        self.mx[x] = self.val[x]
        if l: self.mx[x] = max(self.mx[x], self.mx[l])
        if r: self.mx[x] = max(self.mx[x], self.mx[r])

    def push_rev(self, x):
        self.ch[x][0], self.ch[x][1] = self.ch[x][1], self.ch[x][0]
        self.rev[x] ^= True

    def push_down(self, x):
        if self.rev[x]:
            if self.ch[x][0]: self.push_rev(self.ch[x][0])
            if self.ch[x][1]: self.push_rev(self.ch[x][1])
            self.rev[x] = False

    def rotate(self, x):
        y = self.par[x]
        z = self.par[y]
        k = 1 if self.ch[y][1] == x else 0
        w = self.ch[x][1 - k]
        if not self.is_root(y):
            if self.ch[z][0] == y: self.ch[z][0] = x
            else: self.ch[z][1] = x
        self.par[x] = z
        self.ch[x][1 - k] = y
        self.par[y] = x
        self.ch[y][k] = w
        if w: self.par[w] = y
        self.push_up(y)
        self.push_up(x)

    def splay(self, x):
        stack = []
        u = x
        stack.append(u)
        while not self.is_root(u):
            u = self.par[u]
            stack.append(u)
        while stack:
            self.push_down(stack.pop())
        while not self.is_root(x):
            y = self.par[x]
            if not self.is_root(y):
                z = self.par[y]
                if (self.ch[z][0] == y) == (self.ch[y][0] == x):
                    self.rotate(y)
                else:
                    self.rotate(x)
            self.rotate(x)

    def access(self, x):
        last = 0
        y = x
        while y:
            self.splay(y)
            self.ch[y][1] = last
            self.push_up(y)
            last = y
            y = self.par[y]
        self.splay(x)
        return last

    def make_root(self, x):
        self.access(x)
        self.push_rev(x)

    def link(self, x, y):
        self.make_root(x)
        self.par[x] = y

    def path_max(self, x, y):
        self.make_root(x)
        self.access(y)
        return self.mx[y]

    def update_val(self, x, v):
        self.access(x)
        self.val[x] = v
        self.push_up(x)


def main():
    N = int(input())
    lct = LCT(N + N)  # 頂点 1..N + 辺ノード N+1..2N-1

    edge_node = {}

    for i in range(N - 1):
        u, v, w = map(int, input().split())
        eid = N + i + 1  # 辺ノード番号 (1-indexed)
        lct.val[eid] = w
        lct.mx[eid] = w
        edge_node[(min(u,v), max(u,v))] = eid
        lct.link(u, eid)
        lct.link(eid, v)

    Q = int(input())
    out = []
    for _ in range(Q):
        line = list(map(int, input().split()))
        if line[0] == 1:
            _, u, v, w = line
            eid = edge_node[(min(u,v), max(u,v))]
            lct.update_val(eid, w)
        else:
            _, u, v = line
            out.append(lct.path_max(u, v))

    print('\n'.join(map(str, out)))

main()

Step-by-Step 解説

1辺重みを頂点値として管理
LCT は本来頂点値を扱う。辺 $(u,v,w)$ を辺ノード $e$（追加頂点）として $u-e-v$ の経路に変換し、$e$ の val を $w$ とする。頂点ノードの val = 0 にすることで、path_max はパス上の辺ノードの val の最大を返す。

2LCT の Splay Tree 部分
各 preferred path を Splay Tree で管理。ノード $x$ が「aux tree の根」か否かは is_root(x) で判定（親が $x$ を子として持たないか）。

3access(x) 操作
$x$ から LCT の根まで preferred path を繋ぐ。各 aux tree の根に splay し、右の子を繋ぎ替えながら遡る。

4path_max(x, y) の実装
make_root(x) で $x$ を根にし、access(y) で $x$-$y$ パスを1つの Splay Tree に収める。その根の mx 値が答え。

5辺重み更新
辺ノード $e$ の val を変更し、access(e) でその祖先の mx 値を再計算する。

計算量

構築: $O(N \log N)$ amortized
path_max クエリ: $O(\log N)$ amortized
辺重み更新: $O(\log N)$ amortized
全体: $O((N + Q) \log N)$ amortized

よくあるミス

ミス	原因	正しい書き方
is_root の判定が逆	子の判定と根の判定を混同	親が自分を ch[0] か ch[1] に持てば非根
push_down を splay の前にスタックで実行しない	反転フラグが子に伝播しないまま rotate	splay 前に根までのパスを逆順で push_down
辺ノードの番号衝突	頂点 1..N と辺ノードが重複	辺ノードは N+1 以降の番号を使う
link 後に mx 値を更新しない	リンク後の集約値が古い	link 内か直後に push_up

次のステップ

発展問題: LCT による動的木の連結性チェック + パス上の辺重みの和クエリ
関連: Day009 Q5（Link-Cut Tree 基礎実装）の復習
応用: ネットワークの帯域変更に対するリアルタイムボトルネック検出

自己評価

完全理解おおむね理解要復習