概要

区間和の合同条件を「差分の等式」に変換し、版が木状に分岐する構造を DFS でたどりながら、重み付き Union-Find（rollback 付き）で整合性判定・値の確定判定を行う問題です。

考察

この問題の核心は、区間和 [ (A_L+\cdots+A_R)\bmod K ] をうまく扱うことです。

まず累積和（mod \(K\)）を [ S_i = (A_1+\cdots+A_i)\bmod K,\quad S_0=0 ] と置くと、 [ (A_L+\cdots+A_R)\bmod K = (SR-S{L-1})\bmod K ] なので、主張 score(L,R)=X は [ SR - S{L-1} \equiv X \pmod K ] という「2点間の差の制約」になります。

---

素朴に各版ごとに制約集合をコピーして判定すると、版数が最大 \(10^5\) なので到底間に合いません。
また、クエリは「版 \(B\) を親として版 \(i\) を作る」ので、版全体は木になります（0 が根）。

この構造を使って：

• 版木を DFS で探索
• DFS で辺を下るとき制約を追加
• 戻るとき制約を取り消す（rollback）

とすると、各版の状態を効率よく再現できます。

---

差分制約の管理には、重み付き Union-Find を使います。
各ノード \(x\) に対して「親との差分」を持たせ、同一連結成分なら [ S_y-S_x \pmod K ] を計算できます。

• 種類0（追加主張）
  [ SR-S{L-1}=X ] を unite(L-1, R, X) として追加。
  既に同じ成分なら矛盾チェック、別成分なら併合。

• 種類1（質問）
  \(L-1\) と \(R\) が同じ成分なら差分は一意に決まるのでその値を出力。
  別成分なら UNKNOWN。

これで「受理可能か」「一意に定まるか」を正しく処理できます。

アルゴリズム

1. クエリを読み込み、children[B].push_back(i) で版木を構築する。
2. ノードは \(0..N\)（累積和 \(S_0..S_N\)）を使う。
3. rollback 可能な重み付き DSU を用意：
   • findp(x) : 根と \(S_x-S_root\) を返す
   • unite(x,y,w) : \(S_y-S_x=w\) を追加、矛盾なら false
   • queryDiff(x,y) : 同成分なら \(S_y-S_x\) を返す
   • snapshot()/rollback() : 履歴管理
4. 版木を DFS：
   • 子版へ入る前に snap = snapshot()
   • クエリ処理
     • type 0: unite(L-1, R, X)
       

          - 成功: `YES`
          - 失敗: `NO`（状態は実質変化なし）
       

     • type 1: queryDiff(L-1, R)
       

          - 取得可: 値を出力
          - 不可: `UNKNOWN`
       

   • 子孫を処理後、rollback(snap) で元の版状態に戻す
5. 各クエリの答えを順に出力。

計算量

• 時間計算量: \(O((N+Q)\log N)\) 程度（union by size による find 深さを考慮）
• 空間計算量: \(O(N+Q)\)（DSU配列・履歴・版木）

実装のポイント

• 区間 \([L,R]\) は必ず (L-1, R) の差分に変換する。

• mod 計算は負になり得るので、(x % K + K) % K で正規化する。

• rollback 用履歴には「何も変化しなかった操作」も積んでおくと実装が安定する（このコードでは b=-1）。

• type 0 で矛盾して NO の場合、版内容は親と同じ。DFS はそのまま進めてよい（rollback で状態は保たれる）。

  ソースコード

#include <bits/stdc++.h>
using namespace std;

struct RollbackDSU {
    int n;
    long long K;
    vector<int> parent, sz;
    vector<long long> diff; // value[x] - value[parent[x]] mod K

    struct Hist {
        int b, old_parent_b, old_sz_a;
        long long old_diff_b;
    };
    vector<Hist> hist;

    RollbackDSU(int n_=0, long long K_=1): n(n_), K(K_) {
        parent.resize(n + 1);
        sz.assign(n + 1, 1);
        diff.assign(n + 1, 0);
        iota(parent.begin(), parent.end(), 0);
    }

    pair<int,long long> findp(int x) {
        long long acc = 0;
        while (parent[x] != x) {
            acc += diff[x];
            acc %= K;
            x = parent[x];
        }
        return {x, acc}; // value[orig] - value[root]
    }

    int snapshot() const { return (int)hist.size(); }

    void rollback(int snap) {
        while ((int)hist.size() > snap) {
            auto h = hist.back(); hist.pop_back();
            if (h.b == -1) continue;
            int a = parent[h.b]; // currently parent of b is a
            parent[h.b] = h.old_parent_b;
            diff[h.b] = h.old_diff_b;
            sz[a] = h.old_sz_a;
        }
    }

    // enforce: val[y] - val[x] = w (mod K)
    bool unite(int x, int y, long long w) {
        auto [rx, vx] = findp(x); // val[x]-val[rx]
        auto [ry, vy] = findp(y); // val[y]-val[ry]
        w %= K; if (w < 0) w += K;

        if (rx == ry) {
            long long cur = (vy - vx) % K;
            if (cur < 0) cur += K;
            hist.push_back({-1,0,0,0});
            return cur == w;
        }

        // attach smaller to larger
        // need diff[rootChild] = val[rootChild] - val[rootParent]
        if (sz[rx] < sz[ry]) {
            // parent rx -> ry
            // from equation: (val[ry]+vy) - (val[rx]+vx) = w
            // val[rx] - val[ry] = vy - vx - w
            long long d = (vy - vx - w) % K;
            if (d < 0) d += K;

            hist.push_back({rx, parent[rx], sz[ry], diff[rx]});
            parent[rx] = ry;
            diff[rx] = d;
            sz[ry] += sz[rx];
        } else {
            // parent ry -> rx
            // val[ry] - val[rx] = w + vx - vy
            long long d = (w + vx - vy) % K;
            if (d < 0) d += K;

            hist.push_back({ry, parent[ry], sz[rx], diff[ry]});
            parent[ry] = rx;
            diff[ry] = d;
            sz[rx] += sz[ry];
        }
        return true;
    }

    // get val[y]-val[x] if connected
    pair<bool,long long> queryDiff(int x, int y) {
        auto [rx, vx] = findp(x);
        auto [ry, vy] = findp(y);
        if (rx != ry) return {false, 0};
        long long d = (vy - vx) % K;
        if (d < 0) d += K;
        return {true, d};
    }
};

struct Query {
    int type, B, L, R;
    long long X;
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, Q;
    long long K;
    cin >> N >> K >> Q;

    vector<Query> qs(Q + 1);
    vector<vector<int>> children(Q + 1);

    for (int i = 1; i <= Q; i++) {
        int t; cin >> t;
        qs[i].type = t;
        if (t == 0) {
            int B, L, R; long long X;
            cin >> B >> L >> R >> X;
            qs[i] = {t, B, L, R, X};
            children[B].push_back(i);
        } else {
            int B, L, R;
            cin >> B >> L >> R;
            qs[i] = {t, B, L, R, 0};
            children[B].push_back(i);
        }
    }

    RollbackDSU dsu(N + 1, K);
    vector<string> ans(Q + 1);

    function<void(int)> dfs = [&](int v) {
        for (int u : children[v]) {
            int snap = dsu.snapshot();

            auto &qq = qs[u];
            int a = qq.L - 1;
            int b = qq.R;

            if (qq.type == 0) {
                bool ok = dsu.unite(a, b, qq.X);
                if (ok) {
                    ans[u] = "YES";
                    dfs(u);
                } else {
                    ans[u] = "NO";
                    // version u is same as version B => traverse children with base state (no added constraint)
                    dfs(u);
                }
            } else {
                auto [known, d] = dsu.queryDiff(a, b);
                if (known) ans[u] = to_string(d);
                else ans[u] = "UNKNOWN";
                dfs(u);
            }

            dsu.rollback(snap);
        }
    };

    dfs(0);

    for (int i = 1; i <= Q; i++) {
        cout << ans[i] << '\n';
    }
    return 0;
}

---

この解説は gpt-5.3-codex によって生成されました。