結果

問題 No.650 行列木クエリ
ユーザー りあんりあん
提出日時 2018-02-10 00:26:22
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 249 ms / 2,000 ms
コード長 5,791 bytes
コンパイル時間 3,192 ms
コンパイル使用メモリ 224,836 KB
実行使用メモリ 45,676 KB
最終ジャッジ日時 2024-04-17 15:06:27
合計ジャッジ時間 4,764 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
5,248 KB
testcase_01 AC 78 ms
11,836 KB
testcase_02 AC 249 ms
44,340 KB
testcase_03 AC 2 ms
5,376 KB
testcase_04 AC 78 ms
11,520 KB
testcase_05 AC 248 ms
44,420 KB
testcase_06 AC 2 ms
5,376 KB
testcase_07 AC 2 ms
5,376 KB
testcase_08 AC 85 ms
12,672 KB
testcase_09 AC 198 ms
45,676 KB
testcase_10 AC 2 ms
5,376 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<bits/stdc++.h>
using namespace std;
using P = pair<int, int>;
const int M = 1000000007;

struct hl_decomp {
    const std::vector<std::vector<int> >& g;
    int n;
    std::vector<std::vector<int> > chains;
    std::vector<int> parent, subsize, depth, head, last, next, prev, chain, at;

    hl_decomp(const std::vector<std::vector<int> >& g_, int r = -1)
        : g(g_),
          n(g.size()),
          chains(0),
          parent(n, 0),
          subsize(n, 0),
          depth(n, -1),
          head(n, 0),
          last(n, 0),
          next(n, -1),
          prev(n, -1),
          chain(n, -1),
          at(n, 0) {
        if (r != -1) decompose(r);
    }

    // u から根まで登りたいときは
    // for(; u != -1; u = climb(u))
    int climb(int v) const { return parent[head[v]]; }

    // chains[first][second] = v
    std::pair<int, int> get_index(int v) const { return std::make_pair(chain[v], at[v]); }

    int size() const { return n; }

    void decompose(const int root) {
        static int stk[600010];
        int k = 0;
        stk[k++] = root;
        parent[root] = -1;
        depth[root] = 0;

        while (k) {
            int v = stk[--k];
            if (v >= 0) {
                stk[k++] = ~v;
                for (int ch : g[v]) {
                    if (depth[ch] == -1) {
                        depth[ch] = depth[v] + 1;
                        parent[ch] = v;
                        stk[k++] = ch;
                    }
                }
            } else {
                int m = 0;
                v = ~v;
                subsize[v] = 1;
                for (int ch : g[v]) {
                    if (parent[v] == ch) continue;
                    subsize[v] += subsize[ch];
                    if (m < subsize[ch]) {
                        m = subsize[ch];
                        next[v] = ch;
                    }
                }
            }
        }

        k = 0;
        stk[k++] = root;
        while (k) {
            int h = stk[--k];
            for (int e : g[h]) {
                if (parent[h] != e) stk[k++] = e;
            }

            if (chain[h] != -1) continue;
            chains.push_back(std::vector<int>());
            std::vector<int> &path = chains.back();

            for (int cur = h; cur != -1;) {
                path.push_back(cur);
                cur = next[cur];
            }

            for (int i = 0; i < (int)path.size(); i++) {
                int v = path[i];
                head[v] = path.front();
                last[v] = path.back();
                next[v] = i + 1 != (int)path.size() ? path[i + 1] : -1;
                prev[v] = i != 0 ? path[i - 1] : -1;
                chain[v] = chains.size() - 1;
                at[v] = i;
            }
        }
    }

    int lca(int u, int v) {
        while (chain[u] != chain[v]) {
            if (depth[head[u]] > depth[head[v]])
                u = climb(u);
            else
                v = climb(v);
        }
        return depth[u] < depth[v] ? u : v;
    }
};

vector<long long> mul(const vector<long long>& l, const vector<long long>& r) {
    vector<long long> ret(4);
    ret[0] = (l[0] * r[0] + l[1] * r[2]) % M;
    ret[1] = (l[0] * r[1] + l[1] * r[3]) % M;
    ret[2] = (l[2] * r[0] + l[3] * r[2]) % M;
    ret[3] = (l[2] * r[1] + l[3] * r[3]) % M;
    return ret;
}

const vector<long long> ex = { 1LL, 0LL, 0LL, 1LL };


class Segtree {
    int n, s, t;
    vector<vector<long long> > tr;
    vector<long long> q(int k, int l, int r) {
        return r <= s || t <= l ? ex : s <= l && r <= t ? tr[k]
                : mul(q(k << 1 | 1, l, l + r >> 1), q(k + 1 << 1, l + r >> 1, r));
    }

public:
    Segtree() {}
    Segtree(int m) {
        n = 1;
        while (n < m) n <<= 1;
        tr.clear();
        tr.resize((n << 1) - 1, ex);
    }
    void update(int j, const vector<long long>& x) {
        int i = j + n - 1;
        tr[i] = x;
        while (i > 0) { i = i - 1 >> 1; tr[i] = mul(tr[i << 1 | 1], tr[i + 1 << 1]); }
    }
    // [s, t)
    vector<long long> run(int _s, int _t) { s = _s; t = _t; return q(0, 0, n); }
};


int main() {
    int n;
    cin >> n;
    vector<vector<int> > g(n);
    vector<P> edges(n - 1);
    vector<vector<long long> > mats(n - 1);
    map<P, int> edge_ind;
    for (int i = 0; i < n - 1; ++i) {
        int a, b;
        scanf("%d%d", &a, &b);
        g[a].push_back(b);
        g[b].push_back(a);
        edges[i] = P(a, b);
        mats[i] = ex;
        edge_ind[P(min(a, b), max(a, b))] = i;
    }
    hl_decomp hld(g, 0);
    int m = hld.chains.size();
    vector<Segtree> sgs(m);
    for (int i = 0; i < m; ++i) {
        sgs[i] = Segtree(hld.chains[i].size());
    }
    int q;
    cin >> q;
    for (int _ = 0; _ < q; ++_) {
        string h;
        cin >> h;
        if (h == "x") {
            int i;
            cin >> i;
            cin >> mats[i][0] >> mats[i][1] >> mats[i][2] >> mats[i][3];
            int a = edges[i].first, b = edges[i].second;
            if (hld.chain[a] == hld.chain[b]) {
                sgs[hld.chain[a]].update(min(hld.at[a], hld.at[b]), mats[i]);
            }
        }
        else {
            int i, j;
            cin >> i >> j;
            vector<long long> ans = ex;
            while (1) {
                if (hld.chain[i] == hld.chain[j]) {
                    ans = mul(sgs[hld.chain[i]].run(hld.at[i], hld.at[j]), ans);
                    break;
                }
                ans = mul(sgs[hld.chain[j]].run(0, hld.at[j]), ans);
                int h = hld.head[j];
                j = hld.climb(j);
                ans = mul(mats[edge_ind[P(min(j, h), max(j, h))]], ans);
            }
            printf("%lld %lld %lld %lld\n", ans[0], ans[1], ans[2], ans[3]);
        }
    }
    return 0;
}
0