閉路の長さは木の距離に1を足した値
ABC014 D「閉路」は、連結な木の頂点 a と b に新しい辺を1本加えたとき、できる閉路の長さを何度も求める問題です。答えは、元の木で a と b を結ぶ距離に、追加した辺の1を足した値です。各クエリの距離を高速に求めるため、最小共通祖先（LCA）とbinary liftingを使います。
ABC014 D「閉路」の問題文では、頂点数 N とクエリ数 Q がそれぞれ100,000以下です。クエリごとに木全体を探索すると最悪で約100億規模の処理になり得るため、根からの距離と祖先を先に計算しておきます。
公式サンプル1では距離3に1辺を足す
問題の入力例1をそのまま載せます。頂点2と5の間には、木の辺を3本通る経路があります。そこへ新しい辺を加えると、閉路には経路上の3本と新しい1本が含まれます。
5
1 2
1 3
1 4
4 5
3
2 3
2 5
2 4公式出力は次のとおりです。
3
4
3最初のクエリ (2, 3) と3番目の (2, 4) は、どちらも木上の距離が2なので閉路長は3です。2番目の (2, 5) は距離が3なので、出力は4になります。
根・深さ・LCAで経路の折り返し点を見つける
木のどこか1頂点を根にすると、各頂点には根からの親子関係ができます。頂点 v の親は、根から v へ進むとき直前に通る頂点です。深さ depth[v] は根から v までの辺数とします。根は1として考えます。
DFS・BFSの使い分けとPython実装を先に確認したい場合は、AtCoderのDFS・BFSをどう使い分ける？Python実装を3問で学ぶも参考になります。
1
├── 2
├── 3
└── 4
└── 5
根を1にしたサンプルの木では、頂点2の親は1、頂点5の親は4です。depth[2] = 1、depth[5] = 2 となります。LCA（最小共通祖先）は、2頂点から親をたどって到達できる共通の祖先のうち、最も深い頂点です。ここでは頂点2と5のLCAは1で、経路は 2 → 1 → 4 → 5 です。
このクエリでは深さに1の差があるので、深い側の5を親へ1回進めて4にします。頂点2と4は同じ深さになり、どちらの親も1です。したがってLCAは1、距離は depth[2] + depth[5] - 2 × depth[1] = 1 + 2 - 0 = 3 です。公式解説PDFも、深さをそろえてから2頂点を同時に上げてLCAを求める方法を説明しています。
AtCoder Beginner Contest 014の公式解説PDF
親を1段ずつ調べるとクエリ数に比例して重くなる
1回のクエリごとにBFSやDFSをやり直すと、1回あたり最大で O(N) の探索が必要です。木が長い鎖なら、親を1段ずつたどる方法も最長で O(N) かかります。これを最大100,000件のクエリで繰り返すと、最悪計算量は O(NQ) です。
そこで、各頂点から何段かまとめて上がった先を前計算します。1回の親移動を繰り返す代わりに、距離の差やLCAまでの高さを2のべき乗単位で調整できます。
2のべき乗段上の祖先を前計算する
up[k][v] を、頂点 v から親を 2^k 回たどった先とします。up[0][v] は1段上の親です。2段上へ進むには、まず1段上へ進み、そこからさらに1段進めばよいので、次の式で表せます。
up[k][v] = up[k - 1][up[k - 1][v]]
この式は「半分進んだ頂点から、もう半分進む」という意味です。段数の小さい表から作れば、全頂点の祖先を順に計算できます。根の上には実際の親はいませんが、コードでは根の親を根自身にしておきます。こうすると根より上を参照しても添字がはみ出さず、LCAの処理を同じ式で書けます。
| 頂点 | 1段上 up[0] | 2段上 up[1] |
|---|---|---|
| 1 | 1 | 1 |
| 2 | 1 | 1 |
| 4 | 1 | 1 |
| 5 | 4 | 1 |
深さをそろえ、衝突しない範囲で同時に上がる
LCAを求めるときは、まず2頂点の深さを同じにします。深さの差を2進数で表し、立っているビットに対応する up[k] を使えば、必要な段数だけを O(log N) で上がれます。サンプルの頂点2と5なら差は1なので、5を up[0] で1段上げて4にします。
深さをそろえても頂点が異なる場合は、大きい段数から順に調べます。up[k][a] と up[k][b] が異なるなら、2頂点をその段数だけ同時に上げてもLCAを越えません。その位置から先を同じように調べ、最後に残った2頂点の親がLCAです。もし深さをそろえた時点で同じ頂点になったら、その頂点自身がLCAになります。
頂点2と4は、どの段数でたどっても祖先が1で一致します。異なる祖先へ進む必要がないため、直後の親である1がLCAです。別の木でLCAの直下に左右の枝が分かれている場合は、祖先が異なる最大の段数から両方を上げ、分岐点の1段下まで進みます。
距離の式は共通部分を2回引いて求める
LCAを l とすると、a から l までの辺数は depth[a] - depth[l]、b から l までは depth[b] - depth[l] です。2つを足すと、木上の距離は次の式になります。
distance(a, b) = depth[a] + depth[b] - 2 * depth[l]
公式解説PDFのD問題「解法(4/4)」末尾にある表示式は、LCAの深さを1回だけ引いています。辺 1–2、2–3、2–4 の木で (3, 4) を考えると、LCAは2で両頂点の深さは2です。正しい距離は 2 + 2 - 2 × 1 = 2 なので、閉路長は3です。1回だけ引くと距離が3、閉路長が4になります。
根からLCAまでの辺数は、両側の深さに1回ずつ含まれています。そこを2回引くことで、LCAより下にある2本の枝だけが残ります。ABC014 Dの閉路長は、この距離に追加辺1本を足した distance(a, b) + 1 です。
ABC014 Dを解くPython参考コード
次のコードは、入力から木を作り、反復DFSで親と深さを記録し、LCAを前計算表から求めます。提出結果を示すものではなく、問題文の入出力に対応した参考コードです。
import sys
it = iter(map(int, sys.stdin.buffer.read().split()))
n = next(it)
graph = [[] for _ in range(n)]
for _ in range(n - 1):
a = next(it) - 1
b = next(it) - 1
graph[a].append(b)
graph[b].append(a)
parent = [-1] * n
depth = [0] * n
parent[0] = 0
stack = [0]
while stack:
v = stack.pop()
for to in graph[v]:
if to == parent[v]:
continue
parent[to] = v
depth[to] = depth[v] + 1
stack.append(to)
log = n.bit_length()
up = [parent]
for _ in range(1, log):
prev = up[-1]
up.append([prev[prev[v]] for v in range(n)])
def lca(a, b):
if depth[a] < depth[b]:
a, b = b, a
diff = depth[a] - depth[b]
for k in range(log):
if (diff >> k) & 1:
a = up[k][a]
if a == b:
return a
for k in range(log - 1, -1, -1):
if up[k][a] != up[k][b]:
a = up[k][a]
b = up[k][b]
return parent[a]
q = next(it)
answers = []
for _ in range(q):
a = next(it) - 1
b = next(it) - 1
common = lca(a, b)
distance = depth[a] + depth[b] - 2 * depth[common]
answers.append(str(distance + 1))
sys.stdout.write("\n".join(answers) + "\n")前処理後は1クエリあたりO(log N)
木では2頂点間の経路が1本に定まるため、追加辺が作る閉路はその経路と追加辺ででき、長さは距離に1を足した値になります。祖先表の式は、2^(k - 1) 段の移動を2回続けるので、2^k 段上の頂点を正しく表します。深さをそろえた後、LCAの手前まで2頂点を同時に上げるため、最後に残る親が最も深い共通祖先です。
前処理は親・深さを作る O(N) と祖先表を作る O(N log N)、1クエリは深さ調整とLCA探索で O(log N) です。全体は O(N log N + Q log N) 時間、祖先表を含めて O(N log N) メモリで処理できます。反復DFSなので、頂点が一直線につながる木でも再帰の深さに依存しません。
