Hatena::Grouptopcoder

Hiro180の日記

 | 

2016-06-12最近解いた問題

SRM692 Div1 Hard 23:48

<問題概要>

根付き木が与えられる (頂点数<=300000)

全ての部分木に対し、(ある頂点からすべての頂点へのパスの重みの総和)の最小値のXORを求めよ。

<解法>

重心が最小化する頂点なのはまあそれはそうっていう感じで

部分木に対し、重心が求まればパスの重みは求まるので、重心を求めることを考える。(地味に256MB制限が厳しいのでsegtreeに逃げることはできません)

ところで、ある部分木(根をVとする)に対し

すべての部分木サイズがもとの部分木サイズの半分以下ならVが重心になり、そうでないときは

部分木サイズが最大の子(V2とする)の重心の祖先のどれかが重心になることが示せる。

(前者は自明、後者はV2の祖先以外が重心になるとすると、その頂点の部分木サイズは明らかに小さすぎるから矛盾)

よって、(自分から子へのパス重みの総和、重心)を返しつつDFSをすればOK.コスト計算はDoublingでできる。

(重心を求めるフェーズがやばくならないのは、「系列」が変わらない限りO(N)で済むことと、「系列」が変わるときには部分木サイズが倍以上になるからまとめてO(N log N)的な感じだと思います)

 |