全方位木DP
最遠点を求めた後にLink-Cut Treeで回移動する解法で解いてみました。 ここでは、Link-Cut Treeの詳細な説明は割愛し、必要な部分だけを記載します。 詳細は以下のサイトを見るのが良いと思います。 Link-Cut Treeの実装メモ - 日々drdrする人のメモ Lin…
与えられた木を、頂点1を根とする根付き木とみなします。 辺で結ばれた頂点を考えます。頂点の方が根に近いものとします。 根からDFSをすると、での探索が終了した後にに戻ります。 を根とする部分木について、の子孫についてのが求まっているとします。 か…