#1153303 (C++23) No.650 行列木クエリ

• 問題: No.650 行列木クエリ
• ユーザー: K2
• 提出日時: 2026-03-21 00:48:21
• 言語: C++23 (gcc 15.2.0 + boost 1.89.0)
• 結果: AC
• 実行時間: 99 ms / 2,000 ms
• コード長: 4,844 bytes
• コンパイル時間: 7,341 ms
• コンパイル使用メモリ: 390,056 KB
• 実行使用メモリ: 28,108 KB
• 最終ジャッジ日時: 2026-03-21 00:48:35
• 合計ジャッジ時間: 13,573 ms
• ジャッジサーバーID （参考情報）: judge3_0 / judge2_1

ファイルパターン	結果
sample	AC * 1
other	AC * 10

ソースコード

#include <bits/stdc++.h>
#include <atcoder/all>

using namespace std;
using namespace atcoder;

using ll = long long;
// using mint = modint998244353;
using mint = modint1000000007;

template <typename T> using vec = vector<T>;
template <typename T> using pa = pair<T, T>;
template <typename T> using mipq = priority_queue<T, vec<T>, greater<T>>;

#define REP(_1, _2, _3, _4, name, ...) name
#define REP1(i, n) for (auto i = decay_t<decltype(n)>{}; (i) < (n); ++(i))
#define REP2(i, l, r) for (auto i = (l); (i) < (r); ++(i))
#define REP3(i, l, r, d) for (auto i = (l); (i) < (r); i += (d))
#define rep(...) REP(__VA_ARGS__, REP3, REP2, REP1)(__VA_ARGS__)
#define rrep(i, r, l) for (int i = (r); i >= (l); --i)
template <typename T> bool chmax(T &a, const T &b) { return (a < b ? a = b, true : false); }
template <typename T> bool chmin(T &a, const T &b) { return (a > b ? a = b, true : false); }

constexpr int INF = 1 << 30;
constexpr ll LINF = 1LL << 60;
constexpr int mov[4][2] = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};

void solve();

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout << fixed << setprecision(15);
    int T = 1;
    // cin >> T;
    while (T--) solve();
}

// verifyed: https://judge.yosupo.jp/submission/360859
struct HLDecomposition {
  private:
    void dfs_size(int u) {
        size[u] = 1;
        if (G[u][0] == par[u]) swap(G[u][0], G[u].back());
        for (auto &v : G[u]) {
            if (v == par[u]) continue;
            par[v] = u;
            dfs_size(v);
            size[u] += size[v];
            if (size[v] > size[G[u][0]]) swap(v, G[u][0]);
        }
    }

    void dfs_hld(int u, int &k) {
        in[u] = k++;
        for (auto v : G[u]) {
            if (v == par[u]) continue;
            head[v] = (v == G[u][0] ? head[u] : v);
            dfs_hld(v, k);
        }
        out[u] = k;
    }

    // [u -> v)
    vector<pair<int, int>> ascend(int u, int v) const {
        vector<pair<int, int>> res;
        while (head[u] != head[v]) {
            res.emplace_back(in[u], in[head[u]]);
            u = par[head[u]];
        }
        if (u != v) res.emplace_back(in[u], in[v] + 1);
        return res;
    }

    // (u -> v]
    vector<pair<int, int>> descend(int u, int v) const {
        if (u == v) return {};
        if (head[u] == head[v]) return {{in[u] + 1, in[v]}};
        auto res = descend(u, par[head[v]]);
        res.emplace_back(in[head[v]], in[v]);
        return res;
    }

  public:
    vector<vector<int>> G;
    int root;
    vector<int> size, in, out, head, par;
    HLDecomposition(vector<vector<int>> &_G, int _root = 0) :
        G(_G),
        root(_root),
        size(G.size()),
        in(G.size(), -1),
        out(G.size(), -1),
        head(G.size(), root),
        par(G.size(), root) 
    {
        dfs_size(root);
        int k = 0;
        dfs_hld(root, k);
    }

    void path_query(int u, int v, auto &f, bool vertex = false) {
        int l = lca(u, v);
        for (auto&& [a, b] : ascend(u, l)) f(a + 1, b);
        if (vertex) f(in[l], in[l] + 1);
        for (auto&& [a, b] : descend(l, v)) f(a, b + 1);
    }

    void subtree_query(int u, auto &f, bool vertex = false) {
        f(in[u] + !f, out[u]);
    }

    int lca(int u, int v) {
        while (head[u] != head[v]) {
            if (in[u] > in[v]) swap(u, v);
            v = par[head[v]];
        }
        return in[u] < in[v] ? u : v;
    }

    int idx(int u) { return in[u]; }
};

using S = array<array<mint, 2>, 2>;

S op(S a, S b) {
    S res;
    rep(i, 2) rep(k, 2) rep(j, 2) {
        res[i][j] += a[i][k] * b[k][j];
    }
    return res;
}
S e() {
    S res;
    res[0][0] = res[1][1] = 1;
    return res;
}

void solve() {
    int N;
    cin >> N;
    vec<vec<int>> G(N);
    vec<int> U(N - 1), V(N - 1);
    rep(i, N - 1) {
        int a, b;
        cin >> a >> b;
        U[i] = a;
        V[i] = b;
        G[a].emplace_back(b);
        G[b].emplace_back(a);
    }

    HLDecomposition hld(G);
    rep(i, N - 1) {
        if (hld.idx(U[i]) > hld.idx(V[i])) swap(U[i], V[i]);
    }

    segtree<S, op, e> seg(N);

    int Q;
    cin >> Q;
    while (Q--) {
        char q;
        cin >> q;
        if (q == 'x') {
            int i, a, b, c, d;
            cin >> i >> a >> b >> c >> d;
            i = hld.idx(V[i]);
            S x = {array<mint, 2>{a, b}, array<mint, 2>{c, d}};
            seg.set(i, x);
        } else {
            int i, j;
            cin >> i >> j;
            S res = e();
            auto f = [&] (int u, int v) {
                assert(u < v);
                res = op(res, seg.prod(u, v));
            };
            hld.path_query(i, j, f);
            cout << res[0][0].val() << ' '
            << res[0][1].val() << ' '
            << res[1][0].val() << ' '
            << res[1][1].val() << '\n';
        }
    }
}