F - Figures メモ プリュファーコード問題 //下の式は(N-2 )!を掛けるのを忘れている //上の式は(N-2 )!を掛けるのを忘れている プリューファーコードより、各次数(ei)が決まっているときの木の場合の数は (N-2!) / *1というような形になる 上の式は、それに…

C - Tree and LCS メモ まず、単純な場合を考える パスの上では与えられた順列を反転することで類似度を1にできることが分かる 同様に木の場合で考えると、ある頂点を根としたときに その根から分けられる部分木たちSについて そのS達の各頂点を根を中心とし…

Ex - Constrained Tree Degree メモ プリューファー列について調べた するとSi-1をN回組み合わせてN-2を作る問題になり、 出現回数について重複を除くようにすると 指数型母関数で解ける

D - Halftree メモ 木を生成できるような操作列を求めろ。 ここで操作とはu-vに辺を貼ったときに(u+K)%N, (v+K)%Nに辺が貼られるようなものである Nが奇数の時だけ考える k==1の時にパスを作りたくなる また、g=gcd(N, K)でg==1なら、0-KとKずつ増やすことで…

問題概略 木の直径をK以下にしたい。削除するべき頂点の数は最小でいくつか制約 2 1 解法 木には|S|が偶数の時は一つの中心が、奇数の時は2つの中心あり、最大パスがDの時にそれぞれ全体への距離がD/2以下、(D-1)/2以下となる。 最終的な木の中心を決めてや…