木
再帰で解く。 とりあえず、d[x]は最大の深さの分まで求めればいい。それ以降は0が続くので。 頂点xのxを除くすべての子孫についてdが計算済みとして、d[x]を計算する。d[x]のすべての子供だけを見ればd[x]が求まる。つまり、すべての子供yについてd[x][i+1] …
単一始点最短経路問題で、すべての頂点に最短で到達するのに必要な辺だけを選ぶと木になることが知られている(最短経路木)。 なので、この問題では最短経路木を列挙すればいいことがわかる。根でない頂点vに最短距離で到達した時、直前の頂点をuとする。d(x)…
コメント付きコード // 頂点の数、色の数、頂点vに含まれるアイスの数 int N, M, S[300001]; // グラフ, 頂点vに含まれるアイス vi G[300001], C[300001]; // 解, 色iを使ったかどうか int X[300001], use[300001]; int main(){ scanf("%d%d", &N, &M); rep(…
1個の町に複数の警察署がある場合もありうるが、明らかに無意味なので1個の町にはたかだか1個の警察署しか無いとする。 道路で結ばれた町は、全体で木になっている。 ある頂点が複数の警察署でカバーされているとする。そのうち最も近い頂点をu,二番目に近い…
与えられた銀行の関係は木になっていることがわかる。最初にオフラインにする頂点を固定する。この頂点を根とする根付き木を考える。他の頂点をオフラインにするには、すでにオフラインの頂点と隣接していないといけないのであった。よって、親がオフライン…
解法 木の問題は、根付き木にすると見通しが立てやすくなることが多い。 根から再帰的に色を塗っていく。 ある頂点vの色をcur_col, 親の色をpar_colとする。また、部分木vのうち色が決まっているのはvだけとする。子の色を決めたい。問題文中の色を塗る条件…