頂点 \(i\) を根とする部分木のみを考えたときの答えを \(\mathrm{dp}_i\) とします。

例えば、入力例 \(1\) の場合、

• \(\mathrm{dp}_1=(0,1,0,1,2,1,0)\)
• \(\mathrm{dp}_2=(1,2,1)\)
• \(\mathrm{dp}_3=(2)\)
• \(\mathrm{dp}_4=(1)\)

となります。葉に近い頂点から順に \(\mathrm{dp}_i\) を求めていくことを考えます。

頂点 \(i\) と頂点 \(1\) の距離を \(\mathrm{dep}_i\) とすると、頂点 \(i\) が葉であるとき、

• \(\mathrm{dp}_i = (\mathrm{dep}_i)\)

です。そうでないとき、頂点 \(i\) の子を \(\mathrm{ch}_1,\mathrm{ch}_2,\ldots,\mathrm{ch}_k\) とすると、

• \(\mathrm{dp}_i = (\mathrm{dep}_i), \mathrm{dp}_{\mathrm{ch}_1}, (\mathrm{dep}_i), \mathrm{dp}_{\mathrm{ch}_2}, \ldots, \mathrm{dp}_{\mathrm{ch}_k}, (\mathrm{dep}_i)\) をこの順に連結したもの

です。ただし、\(\mathrm{dp}_i\) が辞書順で最小となるように、\(\mathrm{ch}\) を並び替える必要があります。ここで、\(\mathrm{dep}_i\) は \(\mathrm{dp}_{\mathrm{ch}}\) の任意の要素より小さいので、\(\mathrm{ch}\) は \(\mathrm{dp}_{\mathrm{ch}}\) の辞書順で並び替えればよいです。

よって \(O(N^2 \log N)\) で各 \(\mathrm{dp}_i\) を求めることができます。

木上マージテクを使うことで \(O(N \log^2 N)\) に改善でき、十分高速です。

実装例：https://atcoder.jp/contests/nadafes2022_day1/submissions/30752254