Codeforces #408 (Div. 2) C: Bank Hacking

与えられた銀行の関係は木になっていることがわかる。最初にオフラインにする頂点を固定する。この頂点を根とする根付き木を考える。他の頂点をオフラインにするには、すでにオフラインの頂点と隣接していないといけないのであった。よって、親がオフラインでなければならない。親をオフラインにするのに+1だけその子の頂点の強さが増えるのであった。(neighboring)同様に、親の親が存在する頂点は、その親の親をオフラインにするときに強さが+1される。(semi-neighbouring)したがって、

頂点iをオフラインにする時、その強さは以下のようになる。

根の場合はa[i]

根の子はただ1個の親(根)をもつのでa[i]+1

それ以外の頂点は親と、さらにその親も持つのでa[i]+2

このように根を固定するとすべての頂点の強さが定まるので、根を固定したときに必要な強さはこれらの最大値。その最小値を求めればいいことがわかる。

すべての頂点の強さをとりあえずa[i]+2で初期化する。

根を総当りで固定しよう。

根の強さをa[i]に変える。

根の子の強さをa[i]+1

に変える、このとき、頂点の強さの最大値が簡単に求まればいい。

セグメント木で頂点の強さを管理すれば、O(log(n)) で値の更新と最大値取得ができる。よって、全体でO(nlog(n))の時間で間に合う。