2020年4月3日動的計画法動的計画法, , テーマ記事, 競プロ, モノイド, 結合則, 木DP, 部分木, 全方位木DP, 単位元

競技プログラミングでよく出題される木DPについての説明と、それを同じ計算量で全頂点について求められるように応用した全方位木DPについて解説します。

木DP基本的な考え方とイメージ

木DP とは、根を一つ固定した木について、以 ...

2020年3月16日グラフ, 競プロ, LCA, ダブリング, 木の2頂点間の距離, 木のパス上に頂点があるか

最近木においてある頂点の祖先は「親をたどってたどり着ける頂点」を指し、2頂点の共通祖先は「2頂点が共通して持つ祖先」のことを言います。

頂点 u と v の最近共通祖先(LCA: Lowest Common Ancesto ...

2020年3月13日グラフグラフ, , 競プロ, 無向グラフ, 重み付きグラフ, 木の直径

木に存在する2つノード間の最大距離を木の直径と言います。

重み無しの木でも、重み付きの木でも、木の最遠頂点間の距離が直径になります。

重み無しの木の例:

以下は直径が5となる木の例で ...

2020年1月25日AtCoderbit演算, bit全探索, 包除原理, , 余事象, 制約, 600点

問題へのリンク

問題概要

N頂点の木がある。辺を白か黒で塗るとき、以下のような制約をM個満たすような塗り方は何通りか?

制約 i:頂点 \(u_i\) と頂点 \(v_i\) を繋ぐパス上に、黒く塗られた辺が1つ ...

2019年11月30日AtCoderグラフ, , 400点, BFS, 辺彩色

問題

木構造について、頂点から見た時に自身から伸びる枝に重複が無いように色を塗る。使う色の数の最小値はいくつか?

問題:D – Coloring Edges on Tree

(木構造はグラフの一種と捉 ...