22B の noya2 です. ずいぶん前に抽象化された全方位木 DP のライブラリの記事を書いたのですが，今回は「木 DP の更新」を扱います.

Static Top Tree と呼ばれるデータ構造があります. 以下，STT と省略します. STT は ABC 351-G Hash on Tree において ABC の想定解法として初めて明示的に扱われました. 公式解説が丁寧に書かれており，その後も STT に関する出題や上位勢による積極的な言及もあったことから，約 2 年の月日が経ったいま，STT はだんだんと典型になっているように感じます.

つい最近行なわれた The 2026 ICPC Asia Pacific Championship において，D 問題に STT を使うだけで解ける問題が出題されました. その少し前に，ICPC 用のお手軽実装がないか，より直接的に木 DP を扱う考え方がないかを検討し，自分なりに納得のいく結果が得られていたため，本番ではすんなり通すことができました. この記事では，木 DP を変形することによって，cluster の概念を経由せずに「 ${\log }^2$ の STT」を理解することを目指します.

木の構成に自由度があり，その部分を工夫すると ${\log }^1$ になりますが，工夫せずに segment tree に丸投げすることで実装がかなり楽になっていると主張しています.

木 DP の変形

乱暴な記法や大胆な省略を行なっていますが，察してください.

根付き木上の DP を次のように定式化します.

$$dp[v]=V(v,\underset{vc\in \vec{E}}{⨁}E(vc,dp[c]))$$

• 根付き木を rooted_tree = pair<vertex, set<rooted_tree> > として構成しています.
• $V$ は根付き木に辺をつけたようなものの集合（ set<rooted_tree> ）に根を付け加える関数です.
• $E$ は根付き木の根に親に伸びる辺をつけたようなものの単元集合を生成する関数です.
• $\oplus$ は根付き木に辺をつけたようなものの集合どうしの非交和を取る関数で，集合を列だと思うことにすると可換モノイドです.

次に，$v$ が葉でないときに，$v$ のある子 $h$ を特別視します.

$$dp[v]=V(v,E(vh,dp[h])\underset{vc\in {\vec{E}}_{-}}{⨁}E(vc,dp[c]))$$

そして，関数 $f_v$ を次のように定義します.

$$f_v(x)=V(v,E(vh,x)\underset{vc\in {\vec{E}}_{-}}{⨁}E(vc,dp[c]))$$

このもとで $dp[v]$ は

$$dp[v]=f_v(dp[h])$$

と書けます. $v$ が葉であるときは $f_v(x)$ は定数で，

$$f_v(x)=V(v)(=dp[v])$$

とします. 特別視した子を辿って $v$ から葉まで至る列を $v,h,\dots ,l$ とすると，

$$\begin{array}{rl}dp[v]& =f_v(f_h(\dots f_l(\epsilon )))\\ & =(f_v\circ f_h\circ \cdots \circ f_l)(\epsilon )\end{array}$$

となります. HLD は最も大きな部分木を持つ子を特別視していくつかの heavy path に分解する手法ですが，ここでの $v,h,\dots ,l$ は $1$ つの heavy path に乗っているということになります. つまり，heavy child に優先的に潜る dfs による dfs order で $f_{\cdot }$ たちの関数合成を segment tree に乗せれば，$f_v\circ f_h\circ \cdots \circ f_l$ は segment tree 上の区間取得で計算できます.

木 DP の更新とは，$V$ や $E$ が更新されるということです. これらの更新に対して $f_v$ たちの更新を追従させることを目指します. たとえば，頂点 $v$ が与えられて，$V(v,\cdot )$ の値のみが更新されたとします. このとき，

• $v$
• $v$ の属する heavy path の最も根に近い頂点（top） $t$ の親 $v^{\prime }$
• $v^{\prime }$ の属する heavy path の top $t^{\prime }$ の親 $v^{\prime \prime }$
• $\dots$

に対応する $f_{\cdot }$ が更新されます. これらの更新点の個数は HLD の計算量解析と同じで根付き木の頂点数に対して対数です. $f_t$ は更新されませんが，$f_v$ の更新に伴って $dp[t]$ が更新されるため，これを $f_{v^{\prime }}$ の更新に反映する必要があります. この際，${⨁}_{vc\in {\vec{E}}_{-}}$ を再計算するわけにはいかないので，この差分更新は工夫する必要があります. $\oplus$ に逆元が存在する場合は簡単ですが，一般には $\oplus$ を乗せた segment tree の一点変更として処理することになります. この segment tree には，ある頂点の軽い子 $c$ が連続して並ぶような順序（たとえば bfs order）で $E(vc,dp[c])$ を乗せておけばよく，このとき $⨁$ の計算は区間取得になります.

各更新では，次のものがその時点の計算結果として正確に保持されています.

• すべての頂点 $v$ に対する $f_v$
• すべての頂点 $v$ に対する ${⨁}_{vc\in {\vec{E}}_{-}}E(vc,dp[c])$
• すべての heavy path の top $t$ に対する $dp[t]$

$f_v$ を関数合成を乗せた segment tree で，$E(vc,dp[c])$ を $\oplus$ を乗せた segment tree でそれぞれ管理すれば，$\log$ が $2$ つくらいの時間計算量で更新に追従できます.

例：The 2026 ICPC Asia Pacific Championship - D. Christmas Tree Un-decoration

問題はこちら（Codeforces）

$dp[v]:=$ $v$ を根とする部分木で必要な回数 とすると，遷移は

$$dp[v]=\max (x_v,\sum _{vc\in \vec{E}}dp[c])$$

となります. わざわざあてはめる方が分かりにくいと思いますが，上の定式化で対応するものを書いてみます.

• $V(v,E)=\max (x_v,E)$
• $E(e,V)=V$
• $\oplus =+$

のような感じになると思います. 記号は雰囲気で使っています. 今回は $E$ が $e$ を使わずに $V$ をそのまま返すので，もっと簡単です.

$v$ が葉でないとき，$v$ の子として $h$ を特別視して

$$dp[v]=\max (a_v,dp[h]+\sum _{vc\in {\vec{E}}_{-}}dp[c])$$

と書けます.

$$f_v(x)=\max (a_v,x+\sum _{vc\in {\vec{E}}_{-}}dp[c])$$

とすると，$dp[v]=f_v(dp[h])$ です.

$v$ が葉のときは $f_v(x)=\max (a_v,x-\infty )$ とします. $f_v(x)=a_v$ としても良いですが，$f_v$ を（平行移動つきの）clamp として統一的に扱うことにします.

clamp どうしの合成は clamp です. したがって，関数合成は簡単に計算・保持できます.

クエリでは $x_v$ が更新されますが，これに応じて $f_{\cdot },dp[t]$ を更新します.

• まず，$f_v$ が更新されます.
• 次に $v$ の属する heavy path の top $t$ について $dp[t]$ が更新されます.
• それに伴って，$t$ の親 $v^{\prime }$ について $f_{v^{\prime }}$ が更新されます.
• ...

$dp[t]$ が更新されたとき，$f_{v^{\prime }}$ を更新することは，$v^{\prime }$ について ${\sum }_{vc\in {\vec{E}}_{-}}dp[c]$ を保持しておくことで，差分更新できます. $+$ が逆元を持っているおかげで，$\oplus$ を集約する segment tree は不要になっています.

これで，$x_v$ の変更にすべての変更が追従できました. 最初なので，実装を載せておきます.

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
bool chmin(auto &a, auto b){ return a > b ? a = b, 1 : 0; }
bool chmax(auto &a, auto b){ return a < b ? a = b, 1 : 0; }

template<class S, auto op, auto e>
struct segtree {
    int sz;
    vector<S> d;
    segtree(vector<S> a){
        int n = a.size();
        sz = bit_ceil<uint32_t>(n);
        d.assign(sz*2,e());
        for (int i = 0; i < n; i++){
            d[sz+i] = a[i];
        }
        for (int i = sz-1; i >= 1; i--){
            d[i] = op(d[i*2],d[i*2+1]);
        }
    }
    void set(int p, S x){
        p += sz;
        d[p] = x;
        while (p > 1){
            p >>= 1;
            d[p] = op(d[p*2],d[p*2+1]);
        }
    }
    S prod(int l, int r){
        l += sz, r += sz;
        S sml = e(), smr = e();
        while (l < r){
            if (l & 1) sml = op(sml,d[l++]);
            if (r & 1) smr = op(d[--r],smr);
            l >>= 1;
            r >>= 1;
        }
        return op(sml,smr);
    }
};

//（平行移動つきの）clamp
struct S {
    // max(a, x + b)
    ll a, b;
    // x = any
    ll eval(){
        return max(a,b);
    }
};

// max(f.a, max(g.a, x + g.b) + f.b)
S op(S f, S g){
    chmax(f.a,g.a+f.b);
    f.b += g.b;
    return f;
}
S e(){
    return S{-1LL<<60,0};
}

void solve(){
    int n, q; cin >> n >> q;
    vector<int> par(n);
    vector<vector<int>> g(n);
    par[0] = -1;
    for (int i = 1; i < n; i++){
        cin >> par[i]; par[i]--;
        g[par[i]].emplace_back(i);
    }
    vector<ll> a(n);
    for (int i = 0; i < n; i++){
        cin >> a[i];
    }
    // ord[v] : dfs で v に訪ずれた時刻
    // leaf[v] : v が属する heavy path の最も深い（根から遠い）頂点
    // top[v] : v が属する heavy path の最も浅い（根に近い）頂点
    vector<int> ord(n), leaf(n), top(n); // <- HLD
    // light[v] : \bigoplus_{vc\in\vec{E}_-} E(vc,dp[c])
    vector<ll> light(n), dp(n); // <- ad-hoc
    {
        auto dfs_sz = [&](auto sfs, int v) -> int {
            int sub = 1;
            int ma = -1, id = -1;
            for (int i = -1; auto u : g[v]){
                i++;
                int ch = sfs(sfs,u);
                if (chmax(ma,ch)){
                    id = i;
                }
                sub += ch;
            }
            if (id != -1){
                swap(g[v][0],g[v][id]); // heavy child を先頭に
            }
            return sub;
        };
        dfs_sz(dfs_sz,0);
        int t = 0;
        auto dfs_hld = [&](auto sfs, int v, int ctop) -> int {
            ord[v] = t++;
            top[v] = ctop;
            if (g[v].empty()){
                leaf[v] = v;
                dp[v] = a[v]; // ad-hoc
                return v;
            }
            leaf[v] = sfs(sfs,g[v][0],ctop);
            for (int u : g[v] | views::drop(1)){
                sfs(sfs,u,u);
                light[v] += dp[u]; // ad-hoc
            }
            dp[v] = max(a[v], dp[g[v][0]] + light[v]); // ad-hoc
            return leaf[v];
        };
        dfs_hld(dfs_hld,0,0);
    }
    segtree<S,op,e> seg([&]{
        vector<S> b(n);
        for (int v = 0; v < n; v++){
            b[ord[v]] = S{a[v],light[v]};
        }
        return b;
    }());
    cout << dp[0] << '\n';
    while (q--){
        int v; cin >> v; v--;
        ll x; cin >> x;
        a[v] = x;
        while (v != -1){
            // f_v update
            seg.set(ord[v], S{a[v], light[v]});
            // dp[t] update
            int t = top[v];
            ll dpt = seg.prod(ord[t],ord[leaf[t]]+1).eval();
            int p = par[t];
            if (p != -1){
                light[p] -= dp[t];
                light[p] += dpt;
            }
            dp[t] = dpt;
            v = p;
        }
        cout << dp[0] << '\n';
    }
}

int main(){
    cin.tie(0)->sync_with_stdio(0);
    int t; cin >> t;
    while (t--){
        solve();
    }
}

例：AtCoder Beginner Contest 351 - G. Hash on Tree

問題はこちら(AtCoder)

$dp$ は問題文中の $f$ とします. 問題文中に遷移が書かれていますが，

$$dp[v]=a_v+\prod _{vc\in \vec{E}}dp[c]$$

です. ただし，葉だけ変であることに注意してください. $f_v$ を経由すれば整合性が取れます. すいません，$V,E$ の型が同じで，これも簡単ですね.

例によって，$v$ が葉でないとき，$v$ の子 $h$ を特別視して，

$$dp[v]=a_v+dp[h]\times \prod _{vc\in {\vec{E}}_{-}}dp[c]$$

と書きます.

$$f_v(x)=a_v+x\times \prod _{vc\in {\vec{E}}_{-}}dp[c]$$

とすることで $dp[v]=f_v(dp[h])$ となります. $f_v$ は affine 変換です. 葉の場合は $f_v(x)=a_v$ とすればよいです. そして，affine 変換どうしの合成は affine 変換です.

$\times$ には逆元がないので，light edge をまとめる方の segment tree も使います.

実装は bfs order 順の segment tree も追加で使う以外はほとんど一緒です.

実装(AtCoderへの提出)

例：Library Checker Point Set Tree Path Composite Sum (Fixed Root)

問題はこちら（Library Checker）

$dp[v].ans:=$ $v$ を根とする部分木で $P(\cdot )$ を定義したときの $P(\cdot )$ の総和

$dp[v].sub:=$ $v$ を根とする部分木の頂点数

とします.

遷移は affine 変換が線形であることを用いていろいろ分解できて

$$\begin{gathered} dp[v].ans=a_v+\sum _{vc\in \vec{E}}(b_{vc}dp[c].ans+c_{vc}dp[c].sub) \\ dp[v].sub=1+\sum _{vc\in \vec{E}}dp[c].sub \end{gathered}$$

と書けます.

先述の定式化においては

• $V(v,E).ans=a_v+E.sum$
• $V(v,E).sub=1+E.sub$
• $E(e,V).sum=b_{vc}V.ans+c_{vc}V.sub$
• $E(e,V).sub=V.sub$
• $\oplus =+$ (ベクトルとしての加算)

です. ようやく辺重みが登場しました.

例によって，$v$ が葉でないとき，$v$ の子 $h$ を特別視して，

$$\begin{gathered} dp[v].ans=a_v+b_{vh}dp[h].ans+c_{vh}dp[h].sub+\sum _{vc\in {\vec{E}}_{-}}(b_{vc}dp[c].ans+c_{vc}dp[c].sub) \\ dp[v].sub=1+dp[h].sub+\sum _{vc\in {\vec{E}}_{-}}dp[c].sub \end{gathered}$$

と書きます.

$$\begin{gathered} f_v(x).ans=a_v+b_{vh}x.ans+c_{vh}x.sub+\sum _{vc\in {\vec{E}}_{-}}(b_{vc}dp[c].ans+c_{vc}dp[c].sub) \\ {f}_v(x).sub=1+x.sub+\sum _{vc\in {\vec{E}}_{-}}dp[c].sub \end{gathered}$$

とすることで $dp[v]=f_v(dp[h])$ となります. $f_v$ は affine 変換です. 葉の場合は $f_v(x).ans=a_v,f_v(x).sub=1$ とすればよいです.

辺 $vc$ の更新があったとき，その辺が heavy edge であるか light edge であるかで，更新すべきものが変わります. heavy edge のときは $f_v$ が更新されます. light edge のときは ${⨁}_{vc\in {\vec{E}}_{-}}E(vc,dp[c])$ が更新されます. いずれの場合も，その先の更新は頂点 $v$ に更新があったものと思って更新していけばよいです.

affine 変換と書きましたが，これは

$$\left(\begin{array}{c}{f}_v(x).ans\\ f_v(x).sub\end{array}\right)=\left(\begin{array}{c}{a}_v+{\sum }_{vc\in {\vec{E}}_{-}}(b_{vc}dp[c].ans+c_{vc}dp[c].sub)\\ 1+{\sum }_{vc\in {\vec{E}}_{-}}dp[c].sub\end{array}\right)+\left(\begin{array}{cc}{b}_{vh}& c_{vh}\\ 0& 1\end{array}\right)\left(\begin{array}{c}x.ans\\ x.sub\end{array}\right)$$

として $2$ 次元ベクトルとして見ています. ここで，これを愚直に表現すると $f_v(x)=A_v+B_{v}x$ として $2$ 次元ベクトル $A_v$ と $2\times 2$ 行列 $B_v$ を持つことになりますが，$2$ 行目は明らかに部分木サイズの情報だけで事足りる上にこれは static なので，削減することで定数倍ではありますが大きく改善するでしょう. そもそも DP をもう少し違う形で書いた方が良いです. ここでは DP で計算するべき値がスカラーではない場合でも扱えることを確認するために，このままにしています.

実装（Library Checker への提出）

部分木サイズが static であることを用いた高速化（Library Checker への提出）

${\log }^1$ への道

heavy path 上の頂点に対する $f_{\cdot }$ を乗せた segment tree には，異なる heavy path に跨がる区間の区間取得が来ることはありません. $\oplus$ を集約する segment tree についても同様のことが言えます. このことから，そもそも集約に通常の segment tree を用いるのは無駄があると言えるでしょう. もう少し無駄を観察してみます.

• $f_{\cdot }$ を集約する segment tree には，heavy path ごとに分割すれば，suffix にしか取得クエリが来ない
• $\oplus$ を集約する segment tree には，特定の頂点の light child ごとに分割すれば，全体にしか取得クエリが来ない

これの改善を突き詰めていくと，完全ではない二分木を segment tree と見なすことで，うまく二分木を構築すると ${\log }^1$ になります. そして，そのことは，HLD が木を heavy path からなる高さが頂点数の対数になる木に分解する手法であったのと同様に，STT が木を cluster からなる高さが頂点数の対数になる二分木に分解する手法であるものとして解釈できるはずです. 筆者は cluster の扱いについて詳しくないため，これ以上のことは書けません.

根付き木の構成として，ここでは，最も一般的だと思われる rooted_tree = pair<vertex, set<rooted_tree> > を採用し，そのまま木 DP の更新を導出しました. と言うのは誤解があり，HLD は rooted_tree = vector<pair<vertex, set<rooted_tree>>> として構成していて，実際のところはこの構成に計算を乗せていると思うことができます. heavy path というのは pair::first だけ取り出した vector<vertex> にあたるものです. 難しいのは辺の情報をどこに乗せるかだと筆者は思っていて，cluster などの概念を学ぶと辺の扱いの見通しが良くなるかもしれません. ここで強調したいのは，「辺の情報は子の方が持つ」のような抽象的（標語的）な理解をする必要はなくて，式変形から直接実装が導出できるということです.

全方位化

少し難しいですが，できます. 気持ちは同じで，「子のうちひとつを特別視する」です.

$N$ 頂点の木を取ります. 全方位木 DP で部分木として扱うものは $3N-2$ 種類です. $N$ 個は各頂点を根にしたときの全体の木に対する DP で，残りの $2N-2$ 個は各辺の各向きについてそれが指す先の頂点を根とするその向きの根付き木です（伝われ〜）.

根をひとつ固定して，辺の親側・子側を定めます. 親から子へ向かう辺 $pv$ について，$pv$ に対応する DP はこれまでの方法ですでに計算できています. 一方 $vp$ に対応する DP はどうでしょうか. この場合は $p$ の親 $q$ を特別視します.

$$dp[vp]=V(p,E(pq,dp[pq])\underset{pc\in \vec{E}\setminus \{pv\}}{⨁}E(pc,dp[c]))$$

$pv$ が heavy edge であるときは $pc\in \vec{E}\setminus \{pv\}$ は $pc\in {\vec{E}}_{-}$ と同値で，${⨁}_{pc\in {\vec{E}}_{-}}E(pc,dp[c])$ は更新できるのでした.

$$g_{vp}(x)=V(p,E(pq,x)\underset{pc\in {\vec{E}}_{-}}{⨁}E(pc,dp[c]))$$

とすると $dp[vp]=g_{vp}(dp[pq])$ です. heavy path に逆向きに $g_{\cdot }$ の関数合成を乗せれば良さそうなことが分かりました. 一方，$pv$ が light edge であるときは，$g_{vp}$ を同様に定義しても $g_{vp}$ の更新はできません. $p$ の次数が大きな場合を考えると分かると思います. このときは諦めて定義通り計算することにします. $E(pc,dp[c])$ はすべて $\oplus$ を集計する segment tree に乗っているので，そこから $pv$ の部分だけ取り除いたものも計算できます. 問題は $dp[pq]$ を求める部分ですが，この部分は再帰的に計算します. この再帰は $p$ が根になるまで続きますが，light edge はそれまでに対数回しか現れないので大丈夫です.

各頂点を根にしたときの DP の値は，その頂点から親に向かう DP が計算できるのなら，当然できます.

全方位にすることで新たに保持して更新に追従するべきものは，heavy edge に対する逆向きの関数 $g_{\cdot }$ だけです.

実装例（Point Set Tree Path Composite Sum）（Library Checker への提出）

他の問題例

UCup の問題

JOI の問題

おわりに

特に数式の扱いが雑になってしまいました. ちゃんと書くと雰囲気を掴むことの邪魔になってしまいそうだった，と言い訳させていただきます. なにか分からないことがあれば X(twitter) で聞いてください. なんでも答えます.