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

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

木の重心

第4回 ドワンゴからの挑戦状 予選 2018 E - ニワンゴくんの家探し (1000 点)

重心分解! 問題へのリンク 問題概要 (インタラクティブ) 頂点の木が与えられる。なお、この木はどの頂点の次数も 以下であることが保証されている。 A さんは、この木のいずれかの頂点 を考えている。その頂点 を当てるゲームを行う。 あなたは最大 14 回の…

AOJ 2667 Tree

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

Codeforces Round #190 (Div. 1) C. Ciel the Commander (R2100)

てんぷら君が解いていたのを見て... 問題へのリンク 問題概要 頂点のツリーが与えられる。 ツリーの各頂点に 'A' 〜 'Z' のラベルを割り当てたい。アルファベット順に rank が低くなっていくものとする ('A' が最高ランク)。 任意の 2 頂点 u, v について、u…

CS Academy 069 DIV2 D - Cover the Tree

本番はツリーDPな方向性に走って詰め切れなかった。ひょっとしたらツリーDPでも解けるのかもしれないが復元が大変そう... CSA 069 DIV2 D Cover the Tree N 頂点からなるツリーが与えられる。 ツリーのすべての辺を最小本数のパスで覆え。そのようなパスの集…