考察
mask x に含まれる bit だけをもつ辺、すなわち w OR x=x の辺だけで 1 から N へ到達できれば、その経路の OR も x の submask である。
到達可能な mask の集合は bit を追加する方向に単調であるため、上位 bit から 0 にできるか試すことで数値として最小の mask を確定できる。
採用する候補: 全30 bitを立てた mask から上位 bit を順に仮消去し、許可辺だけの DSU connectivity が保たれるなら消去を確定する
棄却する候補: 各頂点に数値として最小の OR 値を一つだけ持つ Dijkstra 風緩和
数値が小さい mask が bit 集合として別 mask の subset とは限らず、途中の最小値一つが将来の辺との OR に対して常に優越するとは限らない。
ans=(1<<30)-1 とする。b=29..0 について cand=ans without bit b を作り、(w_i|cand)==cand の辺だけで DSU を再構築する。1,N が連結なら ans=cand とし、最後の ans を出力する。
典型の発動条件
bit ごとの貪欲最小化
発動条件: 実行可能 mask が bit 追加に対して上向き閉集合で、数値最小を求めるとき。
最上位から各 bit を外した候補の実行可能性を判定する。
submask 制約の connectivity
発動条件: path 上の全 edge label の OR を指定 mask 以下に抑えたいとき。
label の立っている bit が mask にすべて含まれる辺だけ残して連結性を見る。
DSU
発動条件: 同じ edge filter で無向グラフの二点連結性だけ判定したいとき。
候補 mask ごとに初期化し、許可辺の端点を union する。
問題固有の要素
OR の値を path cost として直接比較せず、「この bit 集合だけで通れるか」という decision problem にすると単調性が現れる。
別の問題へ持ち帰る視点: bitwise 集約量の最小化では、候補 mask が許可する要素集合を作り、実行可能性 oracle と上位 bit 貪欲を組み合わせる。
正当性
simple path 条件は connectivity 判定を妨げない。許可辺で walk があれば cycle を除いて simple path にでき、その OR は増えない。 ある候補 x が可能なら x に bit を足した mask も同じ経路を許すので、lexicographic な bit 最小化と同様に高位から貪欲決定できる。 各判定は edge label が候補 mask の submask かを調べて DSU で結ぶだけで、全体 O(30(N+M)α(N)) になる。
実装上の注意
- label は bit 0..29 だけなので初期 mask を正確に 2^30-1 とする。各 bit 判定で DSU を初期化し直し、禁止 bit を一つでも含む辺を混ぜない。
復習の核
- 重み0だけの path、低位bitの少ない値と高位bitのある値が競合する path、bridge に特定bitが必要な例を全 simple path 列挙と比較する。
計算量と制約
時間
O(B(N+M)α(N))、B=30、各bit候補をDSUで判定。
空間
O(N+M)。
制約との対応
公式制約の確認範囲: Time limit: 3 sec; Memory limit: 1024 MiB; Constraints: 2\le N\le 2\times 10^5; N-1\le M\le 2\times 10^5; 1\le u_i < v_i\le N; 0\le w_i< 2^{30}; The given graph is connected.; All input values are integers.
出典