木上の累積和・いもす法
AtCoder
AtCoder500点
ABC-E
木
グラフ
いもす法
クエリ(木上)
クエリ処理問題
木上で配っていくDP
累積和
木DP
DP
遅延評価
水色diff
補集合を考える
変数変換して扱いやすい同型な問題を見出す
【問題集】木の探索
【問題集】DFS・BFSのステップアップ
典型要素を詰め合わせた教育的問題
木上の累積和・いもす法
【問題集】累積和・いもす法
これの応用問題って感じだった!! drken1215.hatenablog.com 問題へのリンク 問題概要 頂点数 の木が与えられる。 番目の辺は頂点 と頂点 とを結んでいる。はじめ、各頂点には、値 0 が書き込まれている。以下の 個のクエリを処理したあとの、各頂点に書き…
AtCoder
AtCoder400点
ABC-D
木
木DP
累積和
いもす法
クエリ(木上)
グラフ
クエリ処理問題
木上で配っていくDP
遅延評価
緑色diff
操作後の結果を求める問題
【問題集】DFS・BFSのステップアップ
【問題集】木の探索
典型要素を詰め合わせた教育的問題
木上の累積和・いもす法
【問題集】累積和・いもす法
まさに「the 緑 diff」な問題だと思う。 「木を上手く扱えるか」を問いかける問題。 問題へのリンク 問題概要 頂点の木が与えられる。この木の頂点 1 を根とした根付き木を考える。各頂点には初期状態では 0 という数値が書かれている。以下の 回の操作を行…
AtCoder
旧ARC-C
XOR
木
前処理
累積和
パリティ
青色diff
制約条件:ある値=K
数え上げ問題
解空間:O(N^2)個のペア
解空間:O(N^2)通りの選択肢
木上の累積和・いもす法
XOR について a ^ a = 0 な性質を上手く使う問題として。 問題へのリンク 問題概要 頂点の重み付きツリーが与えられる。 整数 が与えられ、ツリー上のパスであってパス上の重みの XOR 和が となるものが何個あるかを数えよ。 制約 考えたこと 根を 1 つ決め…