けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

重心分解

キーエンス プログラミング コンテスト 2019 E - Connecting Cities (600 点)

めちゃいっぱい解法あってすごい!!!!!!!MST への理解が問われる。 いずれ復習をやり切ってちゃんとしたいが取り急ぎ、分割統治法 Kruskal と、想定解法のみ。 問題へのリンク 問題概要 頂点からなるパスグラフと整数 が与えられる。各頂点には重み が…

AOJ 2667 Tree

オイラーツアー第4弾!!! でもせっかくなので色んな方法で解いてみたのん!!! Euler ツアー クエリの平方分割 HL 分解 重心分解 (未、todo) 問題へのリンク 問題概要 頂点 0 を根とする頂点数 N の根付き木において以下の Q 個のクエリに答えよ。なお初…