SoundHound Inc. Programming Contest 2018 -Masters Tournament- Qual E. + Graph

問題

辺に正の重みがある連結なグラフが与えられる。
いま、以下の条件を満たす頂点に正の整数を書き込みたい。

• どの辺も、両端の頂点の整数の和が辺の重みに等しい

条件を満たす正の整数の書き方は何通りあるか？

制約

• 2 <= 頂点数 <= 10^5
• 1 <= 辺の数 <= 10^5
• 2 <= 辺の重み <= 10^9

解放

頂点に書き込める整数の制約がわからないので、まず、適当に1頂点を選びそこをxと書き込む。
すると、その頂点から辺(重みはsとする)を通って行ける頂点の整数はs-xに決まる。
このように多項式「ax+b」を伝搬していくことを考えると、グラフは連結なのですべての頂点に1つ以上多項式が割りあたる。
答えは、最終的にすべての頂点の条件についてxの下界・上界を見てあげれば、何通りxの書き方があるかがわかる。

頂点に多項式が1つ割りあてられているときは、その多項式が正の整数であること「ax+b > 0」を満たせばいいので、「x > -b/a」を考えれば良い。
頂点に多項式が2つ割りあてられているときは、その2つは同じ値にならなければ矛盾してしまうので、ax+b=cx+dからx = (d-b)/(a-c)でなければならず、「そのxが正の整数であること」と「そのxをax+b、cx+dに入れてもどちらも正の整数になること」を考えれば良い。
(a-c=0や(d-b)/(a-c)が割り切れない場合は解がないので0を返す)
頂点に多項式が3つ以上割りあてられているときは、2つ割りあてられているときと同様にすべての多項式が同じ値にならなければいけないが、3つ以上の異なる多項式だとxは解がないので0を返せば良い。
よって、ループなどで無数に多項式が割りあたるケースは、伝搬中に多項式が3つ以上割りあたる頂点にたどり着いた時点で伝搬を中止し0を返せば、制限時間に間に合う。