hamayanhamayan https://blog.hatena.ne.jp/hamayanhamayan/ はまやんはまやんはまやん https://blog.hamayanhamayan.com/ 競技プログラミング https://atcoder.jp/contests/abc133/tasks/abc133_f 前提知識 LCA クエリ先読み 解説 https://atcoder.jp/contests/abc133/submissions/6312857重要なこととして、制約を簡単にした問題が解けないか考えてみる。 今回で言うと、辺の長さの変更が難しいので、これを抜いてみる。 すると、木の2頂点の距離となる。 これはLCAを使えば解ける。 これを発展させて解いていこう。 LCAを使った典型テクとして、「dist(根,a) + dist(根,b) - 2*dist(根,lca(a,b))」があり、今回も… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fblog.hamayanhamayan.com%2Fentry%2F2019%2F07%2F08%2F213009" title="Colorful Tree [AtCoder Beginner Contest 133 F] - はまやんはまやんはまやん" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> Hatena Blog https://hatena.blog 2019-07-08 21:30:09 rich https://blog.hamayanhamayan.com/entry/2019/07/08/213009 1.0 100%