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

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

ツリーの重心

AOJ 2667 Tree

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

Codeforces 190 DIV1 C - Ciel the Commander (重心分解)

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

CS Academy 069 DIV2 D - Cover the Tree

本番はツリーDPな方向性に走って詰め切れなかったん。ひょっとしたらツリーDPでも解けるのかもしれないが復元が大変そうなん... ツリーの重心に関する理解が足りてないことがわかったので勉強してまとめたのん。 ツリーの重心分解 (木の重心分解) の図解 - Q…