ABC 222 F — Expensive Expense

考察

行先の観光費を、その街に付け足す枝の長さとして表すと、「距離+観光費」を普通の木の距離に変えられる。木では直径の両端だけを見れば全始点の最遠距離が分かるので、この性質を使いたい。ただし、自分の街に付けた枝の先は行先に選べないため、最後にその候補を除く。

街の数を NN とし、元の木で街 ii から街 jj までの道路の通行料の和を d(i,j)d(i,j) と書く。街 jj の観光費を DjD_j とすると、各始点 ii について求める値は

max⁡j≠i{d(i,j)+Dj}\max_{j\ne i}\{d(i,j)+D_j\}

である。始点を一つ固定すれば、木を一巡して全街への距離を求め、行先の観光費を足して最大値を取れる。しかし全始点で繰り返すと O(N2)O(N^2) 時間になり、N≤2×105N\leq 2\times 10^5 には間に合わない。始点によらず使い回せる、少数の行先候補を探したい。

行先の加点を最後の一辺にする

観光費がなければ、木の直径の両端が最遠の行先候補になる。一方、今回は遠さだけでなく行先の観光費も効くので、元の木の直径端をそのまま選ぶ根拠はない。そこで、加点も含めて距離として表せないか考える。

DjD_j は途中の街では払わず、行先 jj でだけ一度足す。この役割に合わせ、各街 jj に新しい頂点 j′j' を作り、長さ DjD_j の辺で結ぶ。j′j' を補助葉と呼ぶ。元の頂点の番号は 1,…,N1,\ldots,N、補助葉 j′j' の番号は N+jN+j とし、拡張した木の頂点数を 2N2N とする。

元の頂点間の経路は変わらないので、拡張木でも距離を同じ記号 dd で表す。元の頂点 ii から補助葉 j′j' への経路は、街 jj まで進み、最後に補助辺を渡る。従って

d(i,j′)=d(i,j)+Djd(i,j')=d(i,j)+D_j

となる。途中の街の補助辺へ寄り道することはなく、行先の加点だけを正確に表せた。求める値は「元の頂点 ii から、自分の補助葉 i′i' 以外の補助葉への最遠距離」である。

直径端の二候補と、自分の補助葉の除外

非負辺長の木では、直径の両端への距離の大きい方が、その頂点からの最遠距離になる。今回は全辺長が正で、元の各頂点には補助葉が付くため、直径の両端は補助葉になる。その両端を s′,t′s',t'、対応する元の街を s,ts,t と書く。

例えば、元の木が街1―街2―街3の一本道で、辺長が順に2、3、観光費が D=(10,2,1)D=(10,2,1) の場合を考える。各街に長さ10、2、1の補助辺が付き、補助葉間の距離は d(1′,2′)=14d(1',2')=14、d(1′,3′)=16d(1',3')=16、d(2′,3′)=6d(2',3')=6 となる。直径端は s′=1′,t′=3′s'=1',t'=3' である。

iid(i,1′)d(i,1')d(i,2′)d(i,2')d(i,3′)d(i,3')答え
110466
2122412
3155115

各行では自分の補助葉への距離を候補から除く。街2では、直径端への距離12と4の大きい方を取ればよい。街1では、そのまま最大値を取ると、自分の補助葉への距離10を答えてしまう。補助葉を付ける変換だけでは、元の条件 j≠ij\ne i はまだ満たしていない。

i≠s,ti\ne s,t なら両端とも合法な行先であり、二候補の最大値が使える。i=si=s なら s′s' を除くが、この場合は反対端 t′t' だけで足りる。s′s' から他の補助葉へ進むには、まず長さ DsD_s の辺を通って ss へ出る。これはどの行先にも共通なので、s′s' から最遠の t′t' は、ss から自分の補助葉を除いた中でも最遠になる。i=ti=t も同様である。この共通部分を引く議論は正当性節で式にする。

三回の木探索で距離配列を作る

非負辺長の木では、任意の頂点から最遠点を一つ選び、その点からもう一度最遠点を選ぶと、直径の両端が得られる。この性質と、両端からの距離配列を次のように使う。

  1. 元の辺に加えて、各 jj と j′=N+jj'=N+j を長さ DjD_j の無向辺で結び、拡張木の隣接リストを作る。
  2. 頂点1から全頂点への距離を求め、最遠の頂点を s′s' とする。この一時的な距離配列は以後不要である。
  3. s′s' から全頂点への距離を配列 dsd_s に保存し、その最遠頂点を t′t' とする。
  4. t′t' から全頂点への距離を配列 dtd_t に保存する。ここで ds[v]=d(s′,v)d_s[v]=d(s',v)、dt[v]=d(t′,v)d_t[v]=d(t',v) である。
  5. s=s′−Ns=s'-N、t=t′−Nt=t'-N を求め、元の各頂点 i=1,…,Ni=1,\ldots,N について、次の値を順に出力する。
ansi={dt[i]i=s,ds[i]i=t,max⁡(ds[i],dt[i])i≠s,t.\mathrm{ans}_i= \begin{cases} d_t[i] & i=s,\\ d_s[i] & i=t,\\ \max(d_s[i],d_t[i]) & i\ne s,t. \end{cases}

一回の距離計算では、始点の距離を0にしてスタックへ入れる。頂点 uu を取り出したら、親以外の隣接頂点 vv に、uu までの距離と辺 uvuv の長さの和を記録して進む。木では経路が一意なので、重みがあっても後から距離を更新し直す必要はない。反復DFSで全辺を一巡すればよく、優先度付きキューは不要である。

典型の発動条件

頂点重みの補助葉への変換

発動条件: 評価が「木の距離+行先だけの加点」であり、加点を最後の一辺へ移せるとき。

行先に補助葉を付ければ通常の距離へ統一できる。元の辺長と加点がともに正なら拡張木も正の辺長を持ち、直径の性質を利用できる。別の問題へ転用するときは、辺長の符号と、どの補助頂点を行先に選べるかを確認する。

木の直径端による全頂点最遠距離

発動条件: 非負辺長の木で、全頂点からの最遠距離を求めたいとき。

直径の両端から距離配列を作ると、始点ごとの探索を二候補の比較に置き換えられる。行先の制限がある場合は、その二候補が合法かを調べ、除外した後も残る候補で最大値を達成できることを別に示す。

問題固有の要素

この問題では、自分の街への旅行を許さない。補助葉へ移した後も i′i' は除外対象であり、直径端がそれに一致する場合だけ分岐が必要となる。

手掛かりは、除外する頂点が葉であることだ。自分の補助葉から他の行先への経路はすべて同じ補助辺から始まる。その共通の長さを引いても行先の優劣は変わらないため、反対の直径端を使える。候補を一つ禁止する別問題でも、このような共通部分があるかを調べる。

正当性

補助葉への辺を加えても木であることは変わらず、元の頂点 ii と補助葉 j′j' の距離は d(i,j)+Djd(i,j)+D_j に等しい。従って、合法な行先 j≠ij\ne i と候補の補助葉 j′≠i′j'\ne i' は一対一に対応する。

全辺長が正なので、葉でない頂点を距離最大の経路の端にすると、その経路が使っていない隣接辺へ延ばして距離を増やせる。よって直径端は葉である。元の頂点の次数は補助葉の追加により2以上なので、拡張木の葉はすべて補助葉である。

非負辺長の木における二回の最遠点探索の性質により、手順2、3で得る s′,t′s',t' は直径端である。また、直径の両端までの距離が最遠距離を与える性質により、どの頂点 ii でも全補助葉への距離は max⁡(ds[i],dt[i])\max(d_s[i],d_t[i]) 以下となる。i≠s,ti\ne s,t なら、この上限を達成する端点も合法なので、そのまま答えになる。

i=si=s の場合を示す。任意の j≠sj\ne s に対して、s′s' は葉なので経路は必ず ss を通り、

d(s′,j′)=Ds+d(s,j′)d(s',j')=D_s+d(s,j')

である。s′,t′s',t' が直径をなすことから

Ds+d(s,j′)=d(s′,j′)≤d(s′,t′)=Ds+d(s,t′)D_s+d(s,j')=d(s',j')\leq d(s',t')=D_s+d(s,t')

となり、両辺の DsD_s を引けば d(s,j′)≤d(s,t′)d(s,j')\leq d(s,t') を得る。t′≠s′t'\ne s' なのでこの上限は合法な行先で達成され、dt[s]d_t[s] が答えになる。i=ti=t も対称に ds[t]d_s[t] が答えである。

各探索では親以外へ一度ずつ進み、始点からの一意経路の辺長を足すため、記録した距離は正しい。以上より、三回の探索と手順5の取り出しで全始点の答えを得る。最遠点が同率ならどれを選んでも直径端の性質が成り立つ。N=2N=2 でも両端は二つの補助葉であり、各始点で反対側の街だけが残る。

実装上の注意

  • 元の頂点は 1,…,N1,\ldots,N、補助葉は N+1,…,2NN+1,\ldots,2N。隣接リストと距離配列は添字 2N2N まで確保する。両端の番号から NN を引いて、対応する街を得る。
  • ds[i]d_s[i]、dt[i]d_t[i] は補助辺の長さを既に含む。答えを取り出す際に観光費をもう一度足さない。自分の葉への距離は、0でなく DiD_i なので、正という理由だけでは合法と判断できない。
  • 距離と加算は最初から符号付き64 bit整数で扱う。拡張木の単純経路は、元の辺を高々 N−1N-1 本、補助辺を高々2本通るため、その長さは (N+1)×109(N+1)\times 10^9 以下だが、32 bit整数には収まらない。
  • 一本道では探索の深さが O(N)O(N) になる。反復DFSなら再帰の深さ制限を避けられる。親の番号を一緒に保持し、無向辺を逆向きに戻らないようにする。

復習の核

  • 「距離+行先だけの加点」は、行先に付ける最後の一辺で表せないか考える。
  • 全始点で同じ探索を繰り返す前に、直径端などの少数の基準点で最大値を代表できるか調べる。
  • 変換前の禁止条件も移す。自分の補助葉を除く際は、共通の辺長を引いても最遠の行先が変わらないことが鍵になる。

計算量と制約

時間

拡張木は 2N2N 頂点、2N−12N-1 辺。隣接リストの構築、三回の探索、最遠点の選択、全 NN 個の答えの出力はいずれも O(N)O(N) 時間なので、全体で O(N)O(N)。

空間

拡張木の隣接リスト、距離配列、探索スタックはいずれも O(N)O(N)。全頂点間の距離は保持せず、入力を含む全体の空間は O(N)O(N)。

制約との対応

2≤N≤2×1052\leq N\leq 2\times 10^5、道路の通行料と観光費はともに1以上 10910^9 以下の整数である。拡張後も高々 4×1054\times 10^5 頂点なので、線形時間・空間で処理できる。正の辺長という条件は、最遠点探索と直径端の性質、および元の頂点が直径端にならないことに使う。N≥2N\geq 2 なので、自分の補助葉を除いた行先は必ず存在する。

出典

分類・前提・執筆情報

掲載状態: 収録済み

Expensive Expense の公式問題ページ(外部リンク)

最終確認:

学習上の位置付け

主題の単元: 基準点からの木距離・剰余類・直径・中心

主題
追加で学ぶ技能
    なし
    既習技能
      なし

      主タグ: 木距離・直径・中心・最遠点

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

      学習の位置

      体系上の位置: 基準点からの木距離・剰余類・直径・中心

      • 一回または二回の木探索で少数の基準点からの距離を求め、一意経路・直径端点・中心の性質から頂点分類や最遠距離条件を整理できる。

      この解説で扱わないこと:

      • 根付き木の子状態を合成する木DP、およびLCA・HLDによるパスの区間分解。

      学習記録

      状況更新: 更新記録なし

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

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

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

      同じ単元の問題