kanpurin https://blog.hatena.ne.jp/kanpurin/ かんプリンの学習記録 https://kanpurin.hatenablog.com/ 競技プログラミング 解説 ABC 動的計画法 グラフ 問題はこちら 問題概要 思考の流れ 提出プログラム 感想 問題概要 頂点の木が与えられる. 木の各辺には色が塗られていて長さはである. このとき, 以下の個の問いに答えよ. 色が塗られている辺の長さがに変更されたと仮定したときの二頂点間の距離を求めよ. (辺の長さの変更はこれ以降の問いには影響しない) 思考の流れ これっぽさがある. kanpurin.hatenablog.com 木上の二頂点間の距離は適当な頂点を根としてLCAを求めることで, 各頂点から根までの距離を求めておくことですぐ求めることができる. しかし今回は辺の長さの変更があるので面倒. すべての色と頂点に関して根からまでに通る… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fkanpurin.hatenablog.com%2Fentry%2F2020%2F04%2F22%2F184429" title="ABC133 F - Colorful Tree - かんプリンの学習記録" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> https://chart.apis.google.com/chart?cht=tx&chl=%7B1%5Cle%20N%5Cle%2010%5E%7B5%7D%7D Hatena Blog https://hatena.blog 2020-04-22 18:44:29 rich https://kanpurin.hatenablog.com/entry/2020/04/22/184429 1.0 100%