CodeChef June Challenge 2016: Chef and Sad Pairs

https://www.codechef.com/JUNE16/problems/SADPAIRS

問題

グラフが与えられる。各頂点は値 G[v] を持っている。頂点 v に接続している辺を削除したグラフにおいて、G[u]=G[v] かつ u と v が異なる連結成分に属するようなペアの数を数えよ。

やったこと

  • 数え上げは$x_1x_2+x_1x_3+\cdots+x_{n-1}x_n=\frac{1}{2}\left((x_1+\cdots+x_n)^2-(x_1^2+\cdots+x_n^2)\right)$を使えば、和の二乗の部分が不変になるので良さそう。
  • 頂点を切断したときグラフが切断されるかどうかでペア数の振る舞いが変わる。
  • 切断した頂点が関節点かどうかが重要。
  • 関節点以外は簡単に計算できる。
  • 二重辺連結成分分解みたいに、関節点を使ってグラフを木に変えられれば解けそう。
  • とりあえず木のときはマージテクやるだけ。
  • どの頂点を除去しても連結な部分グラフで分解する(二重頂点連結成分分解というらしい)。各成分に対し仮想頂点を一個設置し、関節点はすべてその仮想頂点に繋ぐようにする。これでいい感じの木になる。

f:id:pekempey:20160613031654p:plain

  • 木の再帰で stack overflow することが判明。
  • 木 DP なら DFS 木なり BFS 木なりを作ってトポロジカルソートすればできる。
  • lowlink はもっと複雑。純粋な DFS 木ではなくて、DFS の過程で見た辺を順番に保存しておく。euler tour っぽい?

gist.github.com

スタック制限が無駄に厳しくて、無駄にコードが長くなった。