結果

問題 No.650 行列木クエリ
ユーザー sekiya9311sekiya9311
提出日時 2018-02-10 16:02:37
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 469 ms / 2,000 ms
コード長 6,992 bytes
コンパイル時間 2,552 ms
コンパイル使用メモリ 197,772 KB
実行使用メモリ 77,356 KB
最終ジャッジ日時 2024-10-14 14:11:18
合計ジャッジ時間 6,566 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 94 ms
68,328 KB
testcase_01 AC 362 ms
68,992 KB
testcase_02 AC 454 ms
72,304 KB
testcase_03 AC 94 ms
68,204 KB
testcase_04 AC 366 ms
69,004 KB
testcase_05 AC 469 ms
72,300 KB
testcase_06 AC 96 ms
68,224 KB
testcase_07 AC 90 ms
68,184 KB
testcase_08 AC 335 ms
70,016 KB
testcase_09 AC 420 ms
77,356 KB
testcase_10 AC 89 ms
68,224 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>

using namespace std;

class HeavyLightDecomposition {
private:
    int N, pos;
    std::vector<std::vector<int>> G;
    std::vector<int> parent;

    std::vector<int> heavy;                 // next node of heavy path
    std::vector<int> sub_tree_cnt;
    std::vector<int> maximum_sub_tree_cnt;
    std::vector<int> tree_th_num;           // what number of tree ?

    std::vector<int> head;                  // root of SubTree in this node

    // calc SubTree count of this node
    int dfs(const int now, const int prev) {
        parent[now] = prev;
        int sub_tree_all_cnt = 1; // include now node
        int max_sub_tree_cnt = 0;
        for (auto &&nxt : this->G[now]) {
            if (nxt == prev) {
                continue;
            }
            this->depth[nxt] = this->depth[now] + 1;
            const int now_sub_tree_cnt = this->dfs(nxt, now);
            sub_tree_all_cnt += now_sub_tree_cnt;
            if (max_sub_tree_cnt < now_sub_tree_cnt) {
                max_sub_tree_cnt = now_sub_tree_cnt;
                this->heavy[now] = nxt;
            }
        }
        return this->sub_tree_cnt[now] = sub_tree_all_cnt;
    }

    void bfs(const int root, const int th) {
        std::queue<int> que;
        que.emplace(root);
        while (!que.empty()) {
            const int now_head = que.front();
            que.pop();
            for (int now = now_head; now != -1; now = this->heavy[now]) {
                this->tree_th_num[now] = th;
                this->vid[now] = pos++;
                this->inv_vid[this->vid[now]] = now;
                this->head[now] = now_head;
                for (auto &&nxt : this->G[now]) {
                    if (nxt != this->parent[now]
                        && nxt != this->heavy[now]) {
                        // not parent && not same heavy path
                        // == different heavy path && haven't search yet
                        que.emplace(nxt);
                    }
                }
            }
        }
    }

public:
    std::vector<int> vid, inv_vid;          // re numbering node for decompare (vertex_index)
    std::vector<int> depth;
    HeavyLightDecomposition() {}
    HeavyLightDecomposition(int g_size) :
        N(g_size), G(g_size), parent(g_size),
        depth(g_size), heavy(g_size, -1),
        sub_tree_cnt(g_size), pos(0), tree_th_num(g_size),
        head(g_size), vid(g_size), inv_vid(g_size) {}

    void add_edge(const int a, const int b) {
        this->G[a].emplace_back(b);
        this->G[b].emplace_back(a);
    }

    // if forest, tree roots in argument
    void build(const std::vector<int> roots = std::vector<int>(1, 0)) {
        for (int th = 0; th < roots.size(); th++) {
            this->dfs(roots[th], -1);
            this->bfs(roots[th], th);
        }
    }

    // node(vertex) func in [l, r] !!!!!
    void for_each_node(int a, int b, const std::function<void(int, int)> &func) {
        if (this->vid[a] > this->vid[b]) {
            std::swap(a, b);
        }
        func(std::max(this->vid[this->head[b]], this->vid[a]), this->vid[b]);
        if (this->head[a] != this->head[b]) {
            this->for_each_node(a, this->parent[this->head[b]], func);
        }
    }

    // edge func in [l, r] !!!!!
    void for_each_edge(int a, int b, const std::function<void(int, int)> &func) {
        if (this->vid[a] > this->vid[b]) {
            std::swap(a, b);
        }
        if (this->head[a] != this->head[b]) {
            func(this->vid[this->head[b]], this->vid[b]);
            this->for_each_edge(a, this->parent[this->head[b]], func);
        } else {
            if (a != b) {
                func(this->vid[a] + 1, this->vid[b]);
            }
        }
    }
};

template<typename value_type>
class SegmentTree {
private:
    const int n;
    std::vector<value_type> st;
    std::function<value_type(value_type, value_type)> func;
    value_type initVal;
    value_type query(int l, int r, int k, int L, int R) {
        if (R <= l || r <= L) return initVal;
        if (l <= L && R <= r) return st[k];
        value_type res = initVal;
        int h = (L + R) >> 1;
        if (l < h) res = func(res, query(l, r, (k << 1) + 1, L, h));
        if (h < r) res = func(res, query(l, r, (k << 1) + 2, h, R));
        return res;
    }
    void update(int id, value_type el, int k, int L, int R) {
        if (id < L || R <= id) return;
        if (L + 1 == R && id == L) {
            st[k] = el;
            return;
        }
        int h = (L + R) >> 1;
        update(id, el, (k << 1) + 1, L, h);
        update(id, el, (k << 1) + 2, h, R);
        st[k] = func(st[(k << 1) + 1], st[(k << 1) + 2]);
    }
public:
    SegmentTree() : n(-1) {}
    SegmentTree(int _n,
                value_type _initVal,
                std::function<value_type(value_type, value_type)> _func)
        : n(_n), initVal(_initVal), st(_n << 2, _initVal), func(_func){}
    //範囲 [l, r) !!!!!
    value_type query(int l, int r) {
        assert(this->n != -1 && 0 <= l && r <= this->n && l <= r);
        return query(l, r, 0, 0, n);
    }
    void update(int id, value_type el) {
        assert(this->n != -1 && id < this->n);
        update(id, el, 0, 0, n);
    }
};

using mat = vector<vector<long long>>;
mat identity_matrix = {{1LL, 0LL}, {0LL, 1LL}};
constexpr int MOD = 1e9 + 7;
constexpr int MAX = 1e5 + 10;
mat mul(mat a, mat b) {
    mat ret = {{0, 0}, {0, 0}};
    for (int i = 0; i < 2; i++) {
        for (int j = 0; j < 2; j++) {
            for (int k = 0; k < 2; k++) {
                auto buf = a[i][k] * b[k][j] % MOD;
                (ret[i][j] += buf) %= MOD;
            }
        }
    }
    return ret;
}

SegmentTree<mat> st(MAX, identity_matrix, mul);
HeavyLightDecomposition hld(MAX);
vector<pair<int, int>> es;

int main() {
    int n;
    scanf("%d", &n);
    for (int i = 0; i < n - 1; i++) {
        int a, b;
        scanf("%d%d", &a, &b);
        hld.add_edge(a, b);
        es.emplace_back(a, b);
    }
    hld.build();
    int q;
    scanf("%d", &q);
    while (q--) {
        char c[5];
        scanf("%s", c);
        if (c[0] == 'x') {
            int idx;
            scanf("%d", &idx);
            idx = (hld.depth[es[idx].first] > hld.depth[es[idx].second] ? es[idx].first : es[idx].second);
            mat m = identity_matrix;
            for (int i = 0; i < 2; i++) {
                for (int j = 0; j < 2; j++) {
                    scanf("%lld", &m[i][j]);
                }
            }
            st.update(hld.vid[idx], m);
        } else {
            int a, b;
            scanf("%d%d", &a, &b);
            mat res = identity_matrix;
            hld.for_each_edge(a, b, [&](int l, int r) {
                res = mul(st.query(l, r + 1), res);
            });
            for (int i = 0; i < 2; i++) {
                for (int j = 0; j < 2; j++) {
                    printf("%lld%c", res[i][j], (i & j ? '\n' : ' '));
                }
            }
        }
    }
}
0