\(y\) 年後に区画 \(v\) が沈んでいるための必要十分条件は、「海からスタートして、標高が \(y\) 以下の区画のみを通って \(v\) に到達できること」です。よって問題は次の通り読み替えられます。
「パスに対するコストを、通った区画の標高の最大値と定める。各 \(i\) について、海からコスト \(i\) 以下で到達できる区画の個数を求めよ」

この問題は、海を表す頂点のみからなるグラフから始め、標高の低い区画から順に追加する Union-Find により、\(i\) の昇順に求めることができます。

実装例(C++)