WARushスマートフォン用の表示で見るWARushSRMの結果とか、解けた問題のコードを書いていきますこの広告は、90日以上更新していないブログに表示しています。Commander"問題http://codeforces.com/contest/322/problem/E訳シエルはツリーランドの指揮官に就任した。ツリーランドはその名の示すとおり、n個の都市をn-1の双方向の道で繋いであり、2つの任意の都市を結ぶ経路が必ずある、(いわば木構造になっている)。シエルは各都市に士官を配置したい。Zの文字で表されるランクを持っている。よって26階級あることになり、Aが一番良く、Zが一番下である。各ランクの士官は十分な人数がいる。次のような特別なルールがある。xとyという2つの都市に、同じランクの士官が配置されていた場合、xとyを結ぶ経路上に、より高いランクが配置された都市zがなくてはならない。このルールは同じランクの士官の通信を監視できるようにするため設けられている。都市の情報が与えられるので、士官を配置せよ。出来なければそれを示唆する事。10^5チュートリアルを見て木というものは、ある頂点を選んで削除すると、複数の部分木に分割する。木の頂点数の半分以下となるような部分木にできるような頂点を選び、そこにランクの高い順に士官を配置していく。同じランクの都市の経路上にそれよりランクの高い都市があることになる。半分以下に分割しているので、26個のランクがあれば10万なんて余裕で網羅できる。"ABBADiv1"月別アーカイブリンクはてなブログブログをはじめる(無料)お知らせはてなブログをはじめよう!Ekaingさんは、はてなブログを使っています。ブログを報告するスターをつけました引用をストックしましたストック一覧を見る閉じる引用するにはまずログインしてくださいログイン閉じる引用をストックできませんでした。再度お試しください閉じる限定公開記事のため引用できません。