考察
頂点数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.
出典