これの応用問題って感じだった！！ drken1215.hatenablog.com 問題へのリンク 問題概要 頂点数 の木が与えられる。 番目の辺は頂点 と頂点 とを結んでいる。はじめ、各頂点には、値 0 が書き込まれている。以下の 個のクエリを処理したあとの、各頂点に書き…

AtCoder ABC 187 E - Through Path (水色, 500 点)

まさに「the 緑 diff」な問題だと思う。 「木を上手く扱えるか」を問いかける問題。 問題へのリンク 問題概要 頂点の木が与えられる。この木の頂点 1 を根とした根付き木を考える。各頂点には初期状態では 0 という数値が書かれている。以下の 回の操作を行…

AtCoder ABC 138 D - Ki (緑色, 400 点)

頑張って DFS だけで通した！！！ 問題へのリンク 問題概要 頂点数 の Trie 木と、そのうちの 個の頂点集合 が与えられる。 の各頂点 について、トライ木の根から出発して、以下の操作によって到達するまでの最小コストを求めよ。 トライ木の辺を 1 本先に進…

Educational Codeforces Round 83 G. Autocompletion (R2600)

木の走査って 根の方から情報を配っていく 子ノードたちの情報を引っ張ってくる (いわゆる木 DP) という二つの方向性があって、状況に応じてうまいこと使い分けるとよいイメージがある。 問題へのリンク 問題概要 頂点の木があたえられる。木の各頂点を 色に…

AtCoder ABC 133 E - Virus Tree 2 (水色, 500 点)