結果

問題 No.235 めぐるはめぐる (5)
ユーザー lorent_kyoprolorent_kyopro
提出日時 2021-03-21 23:54:14
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 1,372 ms / 10,000 ms
コード長 6,552 bytes
コンパイル時間 3,043 ms
コンパイル使用メモリ 227,784 KB
実行使用メモリ 32,000 KB
最終ジャッジ日時 2024-05-02 07:16:25
合計ジャッジ時間 9,311 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1,372 ms
31,104 KB
testcase_01 AC 877 ms
32,000 KB
testcase_02 AC 1,320 ms
31,380 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
#include <atcoder/lazysegtree>
#include <atcoder/modint>

__attribute__((constructor))
void fast_io() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);
}

class heavy_light_decomposition {
public:
    heavy_light_decomposition(size_t n)
        : n(n),
          tree(n),
          subtree_size(n, 1),
          parent(n),
          in(n),
          out(n),
          chain_head(n),
          built(false) {}

    heavy_light_decomposition(const std::vector<std::vector<size_t>>& tree)
        : heavy_light_decomposition(tree, 0) {}

    heavy_light_decomposition(const std::vector<std::vector<size_t>>& tree,
                              size_t root)
        : n(tree.size()),
          tree(tree),
          subtree_size(n, 1),
          parent(n),
          in(n),
          out(n),
          chain_head(n),
          built(false) {
        assert(root < n);
        build(root);
    }

    void add_edge(size_t u, size_t v) {
        assert(u < n && v < n);
        tree[u].push_back(v);
        tree[v].push_back(u);
    }

    void build(size_t root = 0) {
        dfs_for_size(0, n);
        size_t time = 0;
        chain_head[root] = root;
        dfs_for_hld(root, time);
        built = true;
    }

    size_t operator[](size_t u) const {
        assert(built && u < n);
        return in[u];
    }

    size_t lca(size_t u, size_t v) const {
        assert(built && u < n && v < n);
        while (true) {
            if (in[u] > in[v]) std::swap(u, v);
            if (chain_head[u] == chain_head[v]) return u;
            v = parent[chain_head[v]];
        }
    }

    std::pair<size_t, size_t> subtree_query(size_t u) const {
        assert(built && u < n);
        return {in[u], out[u]};
    }
    
    template <typename F> void subtree_query(size_t u, const F& f) const {
        assert(built && u < n);
        f(in[u], out[u]);
    }

    // when operation is noncommutative

    // S resl = e(), resr = e();
    // size_t w = hld.lca(u, v)
    // hld.node_query(u, w, [&](size_t l, size_t r) { resl = op(resl, rseg.prod(l, r)); });
    // hld.edge_query(w, v, [&](size_t l, size_t r) { resr = op(seg.prod(l, r), resr); });
    // S res = op(resl, resr);

    std::vector<std::pair<size_t, size_t>> node_query(size_t u, size_t v) const {
        assert(built && u < n && v < n);
        std::vector<std::pair<size_t, size_t>> result;
        while (true) {
            if (in[u] > in[v]) std::swap(u, v);
            if (chain_head[u] != chain_head[v]) {
                result.emplace_back(in[chain_head[v]], in[v] + 1);
                v = parent[chain_head[v]];
            } else {
                result.emplace_back(in[u], in[v] + 1);
                return result;
            }
        }
    }

    template <typename F> void node_query(size_t u, size_t v, const F& f) const {
        assert(built && u < n && v < n);
        while (true) {
            if (in[u] > in[v]) std::swap(u, v);
            if (chain_head[u] != chain_head[v]) {
                f(in[chain_head[v]], in[v] + 1);
                v = parent[chain_head[v]];
            } else {
                f(in[u], in[v] + 1);
                return;
            }
        }
    }

    std::vector<std::pair<size_t, size_t>> edge_query(size_t u, size_t v) const {
        assert(built && u < n && v < n);
        std::vector<std::pair<size_t, size_t>> result;
        while (true) {
            if (in[u] > in[v]) std::swap(u, v);
            if (chain_head[u] != chain_head[v]) {
                result.emplace_back(in[chain_head[v]], in[v] + 1);
                v = parent[chain_head[v]];
            } else {
                if (u != v) result.emplace_back(in[u] + 1, in[v] + 1);
                return result;
            }
        }
    }

    template <typename F> void edge_query(size_t u, size_t v, const F& f) const {
        assert(built && u < n && v < n);
        while (true) {
            if (in[u] > in[v]) std::swap(u, v);
            if (chain_head[u] != chain_head[v]) {
                f(in[chain_head[v]], in[v] + 1);
                v = parent[chain_head[v]];
            } else {
                if (u != v) f(in[u] + 1, in[v] + 1);
                return;
            }
        }
    }

private:
    const size_t n;
    std::vector<std::vector<size_t>> tree;
    std::vector<size_t> subtree_size, parent, in, out, chain_head;
    bool built;

    void dfs_for_size(size_t u, size_t p) {
        parent[u] = p;
        if (!tree[u].empty() && tree[u].front() == p)
            std::swap(tree[u].front(), tree[u].back());
        for (size_t& v : tree[u]) {
            if (v == p) continue;
            dfs_for_size(v, u);
            subtree_size[u] += subtree_size[v];
            if (subtree_size[v] > subtree_size[tree[u].front()]) {
                std::swap(v, tree[u].front());
            }
        }
    }

    void dfs_for_hld(size_t u, size_t& time) {
        in[u] = time++;
        for (size_t& v : tree[u]) {
            if (v == parent[u]) continue;
            chain_head[v] = (v == tree[u].front() ? chain_head[u] : v);
            dfs_for_hld(v, time);
        }
        out[u] = time;
    }
};

using mint = atcoder::modint1000000007;
using S = std::pair<mint, mint>;
S op(S a, S b) { return {a.first + b.first, a.second + b.second}; }
S e() { return {0, 0}; }
using F = mint;
S mapping(F f, S x) { return {x.first + f * x.second, x.second}; }
F composition(F f, F g) { return f + g; }
F id() { return 0; }

int main() {
    size_t n;
    std::cin >> n;
    std::vector<int> s(n), c(n);
    for (auto& si : s) std::cin >> si;
    for (auto& ci : c) std::cin >> ci;

    heavy_light_decomposition hld(n);
    for (size_t i = 0; i < n - 1; ++i) {
        size_t u, v;
        std::cin >> u >> v;
        u--; v--;
        hld.add_edge(u, v);
    }

    hld.build();
    std::vector<S> init(n);
    for (size_t i = 0; i < n; ++i) init[hld[i]] = {s[i], c[i]};
    atcoder::lazy_segtree<S, op, e, F, mapping, composition, id> seg(init);

    size_t q;
    std::cin >> q;
    while (q--) {
        int type, z;
        size_t x, y;
        std::cin >> type;
        if (type == 0) {
            std::cin >> x >> y >> z;
            x--; y--;
            hld.node_query(x, y, [&](size_t l, size_t r) { seg.apply(l, r, z); });
        } else {
            std::cin >> x >> y;
            x--; y--;
            mint ans = 0;
            hld.node_query(x, y, [&](size_t l, size_t r) { ans += seg.prod(l, r).first; });
            std::cout << ans.val() << '\n';
        }
    }
}
0