結果

問題 No.650 行列木クエリ
ユーザー 👑 NachiaNachia
提出日時 2020-10-06 22:42:12
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 182 ms / 2,000 ms
コード長 5,578 bytes
コンパイル時間 1,804 ms
コンパイル使用メモリ 175,052 KB
実行使用メモリ 27,044 KB
最終ジャッジ日時 2023-09-27 08:59:39
合計ジャッジ時間 3,511 ms
ジャッジサーバーID
（参考情報） 		judge11 / judge14
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 3 ms
5,612 KB
testcase_01 AC 75 ms
8,180 KB
testcase_02 AC 176 ms
18,004 KB
testcase_03 AC 3 ms
5,628 KB
testcase_04 AC 77 ms
7,796 KB
testcase_05 AC 179 ms
18,224 KB
testcase_06 AC 3 ms
5,908 KB
testcase_07 AC 4 ms
5,764 KB
testcase_08 AC 86 ms
9,596 KB
testcase_09 AC 182 ms
27,044 KB
testcase_10 AC 4 ms
5,584 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<bits/stdc++.h>
using namespace std;
using LL = long long;
using ULL = unsigned long long;
#define rep(i,n) for(int i=0; i<(n); i++)

const ULL M = 1000000007;

struct LC {
    struct RQV { ULL x[4]; };
    struct RQRV {};
    static RQV Zero() { return { {1,0,0,1} }; }
    static RQRV RZero() { return {}; }
    // addition
    static RQV f(RQV a, RQV b) {
        return {
            (a.x[0] * b.x[0] + a.x[1] * b.x[2]) % M,
            (a.x[0] * b.x[1] + a.x[1] * b.x[3]) % M,
            (a.x[2] * b.x[0] + a.x[3] * b.x[2]) % M,
            (a.x[2] * b.x[1] + a.x[3] * b.x[3]) % M
        };
    }
    // update function
    static void uf(RQV& a, RQV b) { a = b; }
    // effect of range queries
    static void ef(RQV& a, RQRV b) {}
    // range query update
    static void ruf(RQRV& a, RQRV b) {}
    struct Node { int l, r, p; RQV V, S; RQRV R; };
    static Node Nil() { return { -1,-1,-1,Zero(),Zero(),RZero() }; }
    vector<Node> V;
    void init(int n) {
        V.assign(n, Node{ -1,-1,-1,Zero(),Zero(),RZero() });
    }
    Node get(int v) {
        if (v == -1) return Nil();
        return V[v];
    }
    void fix(int v) {
        V[v].S = f(f(get(V[v].r).S, V[v].V), get(V[v].l).S);
        ef(V[v].S, V[v].R);
    }
    void spread(int v) {
        ef(V[v].V, V[v].R);
        if (V[v].l != -1) {
            ef(V[V[v].l].S, V[v].R);
            ruf(V[V[v].l].R, V[v].R);
        }
        if (V[v].r != -1) {
            ef(V[V[v].r].S, V[v].R);
            ruf(V[V[v].r].R, V[v].R);
        }
        V[v].R = RZero();
    }
    int rotL(int v) {
        int w = V[v].r;
        spread(v); spread(w);
        if (V[v].p != -1) {
            if (V[V[v].p].l == v) V[V[v].p].l = w;
            if (V[V[v].p].r == v) V[V[v].p].r = w;
        }
        V[w].p = V[v].p;
        V[v].p = w;
        if (V[w].l != -1) V[V[w].l].p = v;
        V[v].r = V[w].l;
        V[w].l = v;
        fix(v); fix(w);
        return w;
    }
    int rotR(int v) {
        int w = V[v].l;
        spread(v); spread(w);
        if (V[v].p != -1) {
            if (V[V[v].p].l == v) V[V[v].p].l = w;
            if (V[V[v].p].r == v) V[V[v].p].r = w;
        }
        V[w].p = V[v].p;
        V[v].p = w;
        if (V[w].r != -1) V[V[w].r].p = v;
        V[v].l = V[w].r;
        V[w].r = v;
        fix(v); fix(w);
        return w;
    }
    void splay(int v) {
        fix(v);
        while (true) {
            int p = V[v].p;
            if (p == -1) break;
            if (V[p].l == v) {
                if (V[p].p == -1) { rotR(p); }
                else if (V[V[p].p].l == p) { rotR(V[p].p); rotR(p); }
                else if (V[V[p].p].r == p) { rotR(p); rotL(V[v].p); }
                else { rotR(p); }
            }
            else if (V[p].r == v) {
                if (V[p].p == -1) { rotL(p); }
                else if (V[V[p].p].r == p) { rotL(V[p].p); rotL(p); }
                else if (V[V[p].p].l == p) { rotL(p); rotR(V[v].p); }
                else { rotL(p); }
            }
            else break;
        }
        spread(v);
    }
    void splayLC(int v) {
        int i = v;
        while (i != -1) { splay(i); i = V[i].p; }
        i = v;
        while (V[i].p != -1) { V[V[i].p].l = i; i = V[i].p; }
        splay(v);
    }
    void link(int v, int p) {
        splayLC(v); splayLC(p);
        V[v].p = p;
    }
    void cut(int v) {
        splayLC(v);
        V[V[v].r].p = -1;
        V[v].r = -1;
    }
    int lca(int u, int v) {
        if (u == v) return u;
        splayLC(u); splayLC(v);
        if (V[u].p == -1) return -1;
        int p = u, ans = u;
        while (V[p].p != -1) {
            if (V[p].p == v) if (V[v].l == p) return v;
            int pp = V[p].p;
            if (V[pp].l != p && V[pp].r != p) ans = pp;
            p = pp;
        }
        return ans;
    }
    void upd(int v, RQV x) {
        splayLC(v);
        uf(V[v].V, x); fix(v);
    }
    void updr(int r, int v, RQRV x, bool in_r) {
        splayLC(v);
        if (v == r) { if (in_r) { ef(V[r].V, x); fix(r); } return; }
        while (V[r].p != -1) {
            if (V[V[r].p].l == r) rotR(V[r].p);
            else rotL(V[r].p);
        }
        if (V[v].r != -1) { ruf(V[V[v].r].R, x); fix(V[v].r); }
        ef(V[v].V, x); fix(v);
        if (in_r) ef(V[r].V, x);
        fix(r);
    }
    RQV query(int r, int v, bool in_r) {
        splayLC(v);
        if (v == r) { if (in_r) { return V[r].V; } return Zero(); }
        while (V[r].p != -1) {
            if (V[V[r].p].l == r) rotR(V[r].p);
            else rotL(V[r].p);
        }
        RQV ans = V[v].V;
        if (V[v].r != -1) { ans = f(V[V[v].r].S, ans); }
        if (in_r) ans = f(V[r].V, ans);
        return ans;
    }
};

int N;
int I[99999];
vector<pair<int, int>> E[100000];
LC G;

void dfs(int p = 0, int pp = -1) {
    for (auto e : E[p]) {
        if (e.first == pp) continue;
        dfs(e.first, p);
        G.link(e.first, p);
        I[e.second] = e.first;
    }
}

int main() {
    cin >> N;
    rep(i, N - 1) {
        int u, v; cin >> u >> v;
        E[u].push_back({ v,i });
        E[v].push_back({ u,i });
    }
    G.init(N);
    dfs();
    int Q; cin >> Q;
    rep(q, Q) {
        char c; cin >> c;
        if (c == 'x') {
            int i; LC::RQV x; cin >> i; rep(j, 4) cin >> x.x[j];
            G.upd(I[i], x);
        }
        if (c == 'g') {
            int i, j; cin >> i >> j;
            auto ans = G.query(i, j, false);
            rep(t, 4) { if (t) cout << " "; cout << ans.x[t]; }
            cout << endl;
        }
    }
    return 0;
}
0