木上で配っていくDP
AtCoder
AtCoder500点
ABC-E
木
グラフ問題
いもす法
クエリ(木上)
クエリ処理問題
木上で配っていくDP
累積和
木DP
DP
遅延評価
水色diff
補集合を考える
変数変換して扱いやすい同型な問題を見出す
これの応用問題って感じだった!! drken1215.hatenablog.com 問題へのリンク 問題概要 頂点数 の木が与えられる。 番目の辺は頂点 と頂点 とを結んでいる。はじめ、各頂点には、値 0 が書き込まれている。以下の 個のクエリを処理したあとの、各頂点に書き…
AtCoder
AtCoder400点
ABC-D
木
木DP
累積和
いもす法
クエリ(木上)
グラフ問題
クエリ処理問題
木上で配っていくDP
遅延評価
緑色diff
操作後の結果を求める問題
愚直シミュレーション
まさに「the 緑 diff」な問題だと思う。 「木を上手く扱えるか」を問いかける問題。 問題へのリンク 問題概要 頂点の木が与えられる。この木の頂点 1 を根とした根付き木を考える。各頂点には初期状態では 0 という数値が書かれている。以下の 回の操作を行…
Codeforces
EducationalCodeforces
DFS
非自明な線形時間
DP
木
木DP
木上で配っていくDP
trie木
最短路問題
最小コスト
場合分け
グラフ問題
各kに対して
辞書順
DP高速化
DP高速化:累積和
累積和
CodeforcesR2600
頑張って DFS だけで通した!!! 問題へのリンク 問題概要 頂点数 の Trie 木と、そのうちの 個の頂点集合 が与えられる。 の各頂点 について、トライ木の根から出発して、以下の操作によって到達するまでの最小コストを求めよ。 トライ木の辺を 1 本先に進…
AtCoder
AtCoder500点
ABC-E
二項係数
数え上げ問題
木
グラフ問題
木DP
各地点について自由度を掛け算していく数え上げ
木上で配っていくDP
水色diff
制約条件:距離K以下の2頂点
木の走査って 根の方から情報を配っていく 子ノードたちの情報を引っ張ってくる (いわゆる木 DP) という二つの方向性があって、状況に応じてうまいこと使い分けるとよいイメージがある。 問題へのリンク 問題概要 頂点の木があたえられる。木の各頂点を 色に…