ABC 340 G — Leaf Color

考察

頂点数2以上の連結誘導subtreeは少なくとも二つのleafを持ち、その共通色cは一意である。色cを固定すると、使われ得るbranch端は色c頂点だけで、必要な分岐関係はそれらとLCAからなるvirtual treeへ圧縮できる。virtual treeで親辺も選ばれるopen状態g_vを考える。子branch選択積P=∏(1+g_child)、ちょうど一子を選ぶ和Q=Σg_childとすると、親接続時は子0ならvがleafなのでg_v=(P-1)+[A_v=c]。vをtopmostとする閉subtreeは子1の時だけvの色条件が必要で、(P-1-Q)+[A_v=c]Qとなる。

採用する候補: 色ごとにvirtual treeを構築し、leaf条件を数える木DPを行う

色cの出現数mに対しO(m)頂点へ縮約でき、全色のvirtual treeサイズ総和をO(N)に抑えられる。

棄却する候補: 各色について元のN頂点tree全体をDPする

色数がO(N)あり、合計O(N^2)になる。

virtual treeで親辺も選ばれるopen状態g_vを考える。

元treeをEuler tourしLCA前計算する。各色cの頂点をtin順に並べ隣接LCAを追加・再sortしてstackでvirtual treeを作る。postorderでP,Q,gを計算し、各vのclosed countを色cの答えへ加算する。全色分のsize≥2 subtree数を合計し、degree 0で条件を満たすN個のsingletonを一度だけ加える。

典型の発動条件

virtual tree

発動条件: 特定色の頂点間の祖先・分岐関係だけが必要で、全元頂点を色ごとに走査したくない。

対象頂点と隣接Euler順LCAを残し、元pathを圧縮辺にする。

境界degreeを持つ木DP

発動条件: connected subtreeのleafだけにmark条件があり、親辺を選ぶかで頂点degreeが変わる。

親へopenな状態とtopmostで閉じる寄与を分け、選択child数0・1・2以上を積と一次和で集計する。

問題固有の要素

圧縮辺内部の頂点は選ばれるならdegree 2でleafにならず、valid subtreeのtopmost leafは色c頂点、branch頂点はLCAなのでvirtual tree上の選択だけで元subtreeを一意に表せる。

別の問題へ持ち帰る視点: path内部が制約対象外のdegreeになる場合、terminalとbranching LCAだけを残す圧縮が数え上げも保つ。

正当性

degree1頂点が同色cの有効subtreeのterminalはc頂点、分岐点はそれらのLCA。圧縮辺内部はdegree2で色条件に無関係なのでvirtual treeが選択を一意保存する。P積とQ一子和で子選択0/1/2以上を区別しtopmostのleaf条件を適用する。size≥2のsubtreeは葉色一意、singletonは最後にN個を足す。

実装上の注意

  • 同色頂点が一つの場合もvirtual treeを作れるようにし、singletonは色ごとに重複加算せず最後にNを足す。P,Qの更新順とmod減算を正規化する。

復習の核

  • N=1、pathで両端同色/異色、starで選ぶleaf色、同色頂点一つ、virtual edgeが長い例を全subset列挙と比較する。

計算量と制約

時間

N頂点。LCA前計算O(N log N)、各色Euler順sort/LCAで総O(N log N)、virtual tree DP総O(N)。

空間

祖先表O(N log N)、全色頂点listとvirtual tree作業O(N)。

制約との対応

公式制約の確認範囲: Time limit: 2 sec; Memory limit: 1024 MiB; Constraints: 1 \leq N \leq 2 \times 10^5; 1 \leq A_i \leq N; 1 \leq u_i \lt v_i \leq N; The graph given in the input is a tree.; All input values are integers.

出典

分類・前提・執筆情報

掲載状態: 収録済み

Leaf Color の公式問題ページ(外部リンク)

最終確認:

学習上の位置付け

主題の単元: virtual tree・auxiliary tree

主題
  • virtual tree・auxiliary tree: 対象頂点と必要なLCAだけをEuler順・stackで結び、元の木上pathを保つvirtual treeを構成できる。
追加で学ぶ技能
    なし
    既習技能

    主タグ: virtual tree・auxiliary tree

    補助タグ: 根付き木DP・部分木集約

    執筆: abc-explanation-author1.1.1 / revision 2

    学習の位置

    体系上の位置: virtual tree・auxiliary tree

    • 対象頂点と必要なLCAだけをEuler順・stackで結び、元の木上pathを保つvirtual treeを構成できる。

    先に読む単元:

    • 根付き木DP・部分木集約 — DPの最小十分状態で得た考え方と実装を再利用し、根付き木DP・部分木集約の発動条件・正当化・境界を重複なく学ぶ。
    • ancestor query・LCA — doubling・binary liftingで得た考え方と実装を再利用し、ancestor query・LCAの発動条件・正当化・境界を重複なく学ぶ。
    • Euler順による部分木区間化 — DFS入退時刻で各部分木を連続区間へ写し、配列上の更新・集約へ変換する。その発動条件と正当化原理を比較可能な独立教材として学ぶ。

    学習記録

    状況更新: 更新記録なし

    復習設定更新: 更新記録なし

    端末内の保存状態を確認しています。

    要復習一覧 / 学習記録のバックアップ / 解説に戻る

    同じ単元の問題