全方位木dp

全方位木dpについてです。

基本的にここにまとまっていて、僕自身もこの記事から学びました。本記事では、これよりもわかりやすく簡潔な実装します。

名前が大げさですが、普通の木dpを少し拡張するだけです。上のサイトの例題 $1$ にもありますが、次のような問題を考えます。

木の各頂点について、その頂点から伸びる各辺それぞれに対して、その辺を使って移動できる最も遠い距離を求めて下さい。$n \leq 10^6$

まずある頂点を根に固定して、普通の木dpをすると、各頂点についてその頂点から子の方向に向かって伸びる各辺に対する答えはすぐに計算できます。

dを求める答え、farを子の中で最も遠い頂点までの距離の最大値とすると、以下のように書けます。

vector<vector<pair<int, int>>> d(n); //(距離, 行き先)
vector<int> far(n);
function<void (int, int)> dfs = [&](int u, int prev) {
        for (auto v : g[u]) if (v != prev) {
                dfs(v, u);
                far[u] = max(far[u], far[v] + 1);
                d[u].push_back({far[v] + 1, v});
        }
};
dfs(0, -1);

さて、あとは各頂点についてその親方向に伸びる辺の答えがわかればよさそうです。そこで、以下のように頂点 $u$ についてはすべての答えが求められている（赤いところが行き先）として、これから頂点 $v$ の答えを求めたいとします。

もし $u$ の行き先の中で最も遠い行き先が $v$ である場合は、明らかにそれを $v$ の答えに含めてはいけないので、$u$ の行き先の中で二番目に大きいものを取れば良いです。逆に $u$ の最大値が $v$ の方向ではない方向でとれるなら、それは $v$ から見てもやはり最大であるはずです。

それをそのまま実装すると以下のようになります。根だけは距離のソートを一番最初にしています。

sort(d[0].rbegin(), d[0].rend());
function<void (int, int)> dfs2 = [&](int u, int prev) {
        for (auto v : g[u]) if (v != prev) {
                if (d[u][0].second == v) { //最大値をとる行き先を見る
                        d[v].push_back({((int) d[u].size() == 1 ? 0 : d[u][1].first) + 1, u});
                } else { 
                        d[v].push_back({d[u][0].first + 1, u});
                }
                sort(d[v].rbegin(), d[v].rend());
                dfs2(v, u);
        }
};
dfs2(0, -1);

((int) d[u].size() == 1 ? 0 : d[u][1].first)のところは、次のような根であって、そこから二番目の距離が存在しないケースに対処しています。

この発想さえわかっていれば、いつもの木dpと同じ感覚で全方位木dpも書けるんじゃないかと思います。

練習問題をおいておくのでぜひやってみてください（ただし重いです）。
F - Black Radius
E - 足のばし