考え方 回答例 考え方入力例として， 3 3 1 2 2 3 3 1を考えると，DFSで辺を作れば$T_{1}$に，BFSで辺を作れば$T_{2}$になることがわかる．すでに頂点をつないだかどうかはsetで管理すれば良い．回答例スタックを使えばDFSになり，キューを使えばBFSになる．…

考え方 回答例（再帰関数） 回答例（スタック） 考え方AtCoder Beginner Contest 220 - YouTube 頂点1からの答えがわかっていれば，頂点1に隣接する頂点$v$の答えは「(頂点1の答え) - ($v$の部分木の頂点数) + (N - $v$の部分木の頂点数)」で求められる．こ…

子ノードの情報を結合してソート 考え方 回答例 子ノードの情報を結合してソートEditorial - Denso Create Programming Contest 2022(AtCoder Beginner Contest 239)の方法． 毎回ソートして間に合う！考え方各頂点$v$に対し，「頂点$v$の部分木に含まれる頂…

実装 基本形 例題 AtCoder Typical Contest 001 参考 実装基本形 p = [-1] * (N + 1) # 親の配列 (いなければ-1), N要素 (1-indexed, P[0]はダミー) def root(x): # 親がいなければ自分(=根)を返す if p[x] < 0: return x # 自分の根 = 親の根 # & パス圧縮 …

考え方 回答例 注 考え方任意の頂点を根として考えて良い．根から順番に深さ方向に辺の色を決めていけば，まだ見ていない辺の色を決めるときに常に始点の色が定まった状態になっている．そこで，根から順番に，子ノードに辺を伸ばしていくことを考える．始点…