定期宣伝

弊社はエンジニアを熱烈募集しています． 以下から気軽にカジュアル面談申し込んでください． 就職・転職を考えている知人にも積極的に宣伝してください．

Spir | Smart scheduling calendar

この勉強会の宣伝もお願いします． 参加者が増えるほど質や頻度が上がると思います． #Acompany競プロ勉強会 で実況や感想，質問を呟くなども．

Slido

以下のリンクから匿名発言が出来ます． 質問だけじゃなく実況なども気軽にしてください．

Join Slido: Enter #code to vote and ask questions

不定期宣伝

5/18（土）13:00~15:30 でコンテスト開きます オンライン！参加無料！！飛び賞含む豪華賞品！！！

【競プロ大会】Acompany Programming Contest(APC) #4 (2024/05/18 13:00〜)

鋭意準備中

木の重心

木に対して「その頂点を取り除いて出来る部分木の最大サイズを最小化する頂点」を重心と呼ぶ．

左の木の赤い頂点を取り除くと，残る部分木の最大サイズは3になる． 最大サイズを2以下にする方法はないので，赤い頂点が重心．

定理

頂点数 $N$ の木から重心を取り除いて出来る部分木の最大サイズは $N/2$ 以下

構成的証明

根付き木として考え，各頂点 $v$ について部分木のサイズを sz[v] とする． 各頂点 $v$ について，その子 $c\in C(v)$ の中で最も sz[c] が大きい頂点を $m_v$ とする．