この問題は、ポテンシャル付き Union Find を使って解くこともできます。

ポテンシャル付き Union Find

ポテンシャル付き Union Find は、\(N\) 頂点からなるグラフと群 \((G,+)\) を扱うデータ構造です。 グラフの辺 \(e\) には \(G\) の元 \(w(e)\) が対応します。 グラフのどの辺 \(e=(u,v)\) にも対応する逆辺 \(-e=(v,u)\) が存在し、\(w(-e)=-w(e)\) です。 次のような操作が行えます。

• \(\operatorname{find}(i)\) ： \(i\) が属する連結成分の代表元 \(v _ i\) と、\(i\) から \(v _ i\) へ向かう辺の重みの合計 \(w _ i\) の組 \((v _ i,w _ i)\) を返す。より形式的には、\(i\) から \(v _ i\) へのパス \(\bm{e}=(e _ 0,\ldots,e _ k)\) について \(w _ i=\displaystyle\sum _ kw(e _ k)\) である。
• \(\operatorname{unite}(i,j,w)\) ： 頂点 \(i\) から頂点 \(j\) へ重み \(w\) の辺を張る。

実装は、Union Find で用いる \(2\) つの配列

• \(\operatorname{parent}[i]\coloneqq i\) の親の頂点番号
• \(\operatorname{size}[i]\coloneqq i\) が \(i\) の属する連結成分の代表元ならその連結成分の大きさ

に加えて

• \(\operatorname{diff}[i]\coloneqq i\) と \(\operatorname{parent}[i]\) を結ぶ辺の重み

を管理するようにすればよいです（Union Find で連結成分の代表元を求める際に辺を張り替えますが、こちらも同様に \(w_i\) が変わらないよう重みに注意しながら辺を張り替えます）。

この問題をどうやって解くか

この問題は inf に気を付ける必要があるためポテンシャル付き Union Find をそのまま用いるだけでは解けませんが、少し修正すると解けるようになります（今回の問題に使えるような形で非零閉路に対応しているようなライブラリを持っている人は、そのまま用いるだけで解けます）。

いま、整数 \(\mathbb{Z}\) に一点 \(\infty\) を加えたものを考え、\(n+\infty=\infty\) および \(-\infty=\infty\) と定めます。 これは群にはなりません。

連結成分の代表元 \(v _ i\) に対して辺 \((v _ i,v _ i)\) が存在し（これは Union Find の標準的な実装で \(\operatorname{parent}[v _ i]=v _ i\) であることに対応します）、対応する連結成分内にポイントをいくらでも増やせる閉路があるとき \(e((v _ i,v _ i))=\infty\)、そうでないとき \(e((v _ i,v _ i))=0\) であるようにします。 これは、ポイントをいくらでも増やせる閉路が生じたときに \(e((v _ i,v _ i))\) の値を更新することで実現できます。

すると、\(\operatorname{find}(i)\) で \(w _ i+e((v _ i,v _ i))\) を返すことで inf を検出することができます。 そうでない場合、属している連結成分が異なれば nan 、等しければ \(w _ i\) の差を出力すればよいです。

\(\left((\mathbb{Z}\cap\left\lbrack-10^{14},10^{14}\right\rbrack)\cup\{\infty\},+\right)\) を適切に計算することは std::optional<long> で無効値を \(\infty\) とした（上で適切に演算を実装した）り、double で nan を \(\infty\) とすることで実現できます。

この方針を用いると辺の追加がオンラインで行われてもよく、計算量は \(O(N+(M+Q)\alpha(M+Q,N))\) 時間です。

実装例は以下のようになります（実装の簡単のため double を用いていますが、std::optional<long> を用いたほうが定数倍は良好そうです）。

#include <iostream>
#include <vector>
#include <numeric>
#include <cmath>
#include <iomanip>

int main() {
    using namespace std;
    unsigned N, M, Q;
    cin >> N >> M >> Q;

    // ポテンシャル付き Union Find
    vector<unsigned> uf_parent(N), uf_size(N, 1);
    vector<double> uf_diff(N);
    iota(begin(uf_parent), end(uf_parent), 0UL);
    // find(i) := 頂点番号の参照をとり、参照を代表元の頂点番号とした上で重みの差を返す
    const auto find{[&uf_parent, &uf_diff](auto &&i) {
        double ret{};
        while (i != uf_parent[i]) {
            ret += uf_diff[i] += uf_diff[uf_parent[i]];
            i = uf_parent[i] = uf_parent[uf_parent[i]];
        }
        return ret + uf_diff[i];
    }};
    // unite(i, j, w) := i -> j に重み w の辺を張る
    const auto unite{[&uf_parent, &uf_size, &uf_diff, &find, infinity{nan("")}](auto i, auto j, double w) {
        w -= find(i);
        w += find(j);
        if (i == j) {
            // 非零の閉路ができたとき、i -> i の重みを ∞(nan) に変更する
            if (w) uf_diff[i] = infinity;
            return;
        }
        if (uf_size[i] < uf_size[j]) swap(i, j);
        else w = -w;
        uf_size[i] += uf_size[j];
        uf_parent[j] = i;
        uf_diff[j] = w;
    }};

    for (unsigned i{}, a, b, c; i < M; ++i) {
        cin >> a >> b >> c;
        unite(a - 1, b - 1, c);
    }

    // 答えを整数として出力
    cout << fixed << setprecision(0);
    for (unsigned i{}, x, y; i < Q; ++i) {
        cin >> x >> y;
        const auto diff{find(--x) - find(--y)};
        if (x != y) cout << "nan" << endl;
        else if (isnan(diff)) cout << "inf" << endl;
        else cout << diff << endl;
    }

    return 0;
}