drken1215 https://blog.hatena.ne.jp/drken1215/ けんちょんの競プロ精進記録 https://drken1215.hatenablog.com/ AtCoder ABC-Ex 橙色diff Union-Find 木 データ構造テク：差分更新 undoつきUnion-Find データ構造 クエリ処理問題 操作:削除 N個のペア値の問題 種類数 高度典型 木の問題に対してパスの場合から考える DFS グラフテク:値A[i]を頂点に持たせる 各kに対して 解空間:O(2^N)通りの選択肢 最大スコア AtCoder625点 最適化問題 undo 付き Union-Find！ 問題へのリンク 問題概要 頂点数 の木が与えられる。各頂点には、数値 の書かれたボールと、数値 の書かれたボールがある。 各 に対して、次の問に答えよ。 パス - 上の各頂点から ボールを 1 個ずつ選んだときの ボールに書かれた数値の種類数の最大値を答えよ。 制約 考えたこと 木に対する問題を解くときには、まずパスについて解くと良い場合が多いと思う。 パスについての問題とは、すなわち「各 に対して か かを選んだときの、数値の種類数の最大値」を求める問題だ。 そして、実はそれはすでに出題されている！ drken1215.hatenablog.com U… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fdrken1215.hatenablog.com%2Fentry%2F2023%2F06%2F10%2F032900" title="AtCoder ABC 302 Ex - Ball Collector (橙色, 625 点) - けんちょんの競プロ精進記録" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> https://cdn.user.blog.st-hatena.com/default_entry_og_image/80936665/1516148889515660 Hatena Blog https://hatena.blog 2023-06-10 03:29:00 rich https://drken1215.hatenablog.com/entry/2023/06/10/032900 1.0 100%