読者です 読者をやめる 読者になる 読者になる

Live Archive 5884 - Strange Regulations

問題

グラフが与えられる(頂点数N<=8000、辺数M<=100000)。
各辺は会社i(1<=i<=C<=100)が管理している。
グラフは単純グラフで、会社が違ったとしても多重辺は存在しない。
グラフは常に次の制約を満たす。

  1. 各会社の辺だけを使う部分グラフは枝分かれが無く、サイクルが無い。

各クエリを順に処理せよ
クエリは3つの整数S1, S2, Kで与えられる。
1. 全体のグラフにおいて頂点S1,S2を結ぶ辺が存在しないならそれを指摘せよ。
2. そうでないならば、その辺が既に会社Kの管理下ならそれを指摘せよ。
3. そうでないならば、その辺を会社Kの管理に変更すると枝分かれができるならそれを指摘せよ。
4. そうでないならば、その辺を会社Kの管理に変更するとサイクルができるならそれを指摘せよ。
5. そうでないならば、その辺を会社Kの管理に変更し、そのことを出力せよ。

解法

LinkCutTree貼るだけ。

LinkCutTreeとは森を扱うデータ構造で、次のinit以外の操作が平均O(log n)できる。

  1. init(n); n頂点(0..n-1)・辺無しの森を作る。
  2. link(v, w); 頂点vとwの間に辺を張る、ただし、v,wが既に連結ならなにもしない。
  3. cut(v, w); 頂点vとwの間の辺を削除する。ただしそのような辺が無いならなにもしない。
  4. connected(v, w); 頂点v, wが連結かどうか判定する。

会社毎にLinkCutTreeを作ると各クエリで2社のLinkCutTreeを更新することになる。
1. クエリの辺が現在どの会社のものであるかはTreeMap等で記憶しておく。
2. 1と同様。
3. 各会社毎の各頂点の次数を配列で記憶しておく。少なくとも一方が次数2なら指摘する。
4. LinkCutTreeで既に連結ならこの辺を追加するとサイクルができることになる。
5. LinkCutTreeで元の会社の辺をcut、新しい会社Kの辺をlinkする。

パスしか扱わないので他の方法もあるかも、ジャッジ解はsplay treeを使っているようなので多分LinkCutTreeと同じ。