結果

問題 No.235 めぐるはめぐる (5)
ユーザー t98slidert98slider
提出日時 2023-01-28 15:49:46
言語 C++14
(gcc 13.2.0 + boost 1.83.0)
結果
AC  
実行時間 1,433 ms / 10,000 ms
コード長 4,877 bytes
コンパイル時間 3,768 ms
コンパイル使用メモリ 152,968 KB
実行使用メモリ 38,524 KB
最終ジャッジ日時 2023-09-11 04:42:33
合計ジャッジ時間 10,359 ms
ジャッジサーバーID
（参考情報） 		judge15 / judge14
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1,433 ms
37,216 KB
testcase_01 AC 950 ms
38,524 KB
testcase_02 AC 1,382 ms
37,456 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <atcoder/all>
using namespace std;
using mint = atcoder::modint1000000007;

using S = pair<mint, mint>;
using F = mint;
S e(){return make_pair(0, 0);}
S op(S l, S r){return make_pair(l.first + r.first, l.second + r.second);}
S mapping(F f, S x){return make_pair(x.first + x.second * f, x.second);}
F composition(F f, F g){return f + g;}
F id(){return 0;}

struct Heavy_Light_Decomposition{
    int N, tim = 0;
    std::vector<int> sz, ent, leader, order, par;
    std::vector<std::vector<int>> G;
    Heavy_Light_Decomposition(std::vector<std::vector<int>> &g) : 
            N(g.size()), G(g), sz(N), ent(N), leader(N), order(N), par(N) {
        dfs_size(0, -1);
        dfs_hld(0);
    }
    const int& operator[](int v) const {
        assert(0 <= v && v < N);
        return ent[v];
    }
    int& operator[](int v) { 
        assert(0 <= v && v < N);
        return ent[v];
    }
    void dfs_size(int v, int p){
        par[v] = p;
        sz[v] = 1;
        if(!G[v].empty() && G[v][0] == p) std::swap(G[v][0], G[v].back());
        for(auto &u : G[v]){
            if(u == p) continue;
            dfs_size(u, v);
            sz[v] += sz[u];
            if(sz[u] > sz[G[v][0]]) std::swap(G[v][0], u);
        }
    }
    void dfs_hld(int v){
        ent[v] = tim++;
        order[ent[v]] = v;
        for(auto &u : G[v]) {
            if(u == par[v]) continue;
            leader[u] = (G[v][0] == u ? leader[v] : u);
            dfs_hld(u);
        }
    }
    int la(int v, int k) {
        while(true) {
            int u = leader[v];
            if(ent[v] - k >= ent[u]) return order[ent[v] - k];
            k -= ent[v] - ent[u] + 1;
            v = par[u];
        }
    }
    int lca(int u, int v) {
        do{
            if(ent[u] > ent[v]) std::swap(u, v);
            if(leader[u] == leader[v]) return u;
            v = par[leader[v]];
        }while(true);
    }
    //(頂点u, 頂点v, 単位元, 列に対するクエリの収得, 列と列の結合, 辺か頂点か)
    template< typename T, typename Q, typename F >
    T query(int u, int v, const T &identity, const Q &qf, const F &f, bool edge = false) {
        T ans = identity;
        do{
            if(ent[u] > ent[v]) std::swap(u, v);
            if(leader[u] == leader[v]) break;
            ans = f( qf(ent[leader[v]], ent[v] + 1), ans);
            v = par[leader[v]];
        }while(true);
        return f( qf(ent[u] + edge, ent[v] + 1), ans);
    }
    //u -> lhs -> rhs -> vで演算を走らせる
    //セグ木を作る場合は
    //up_f(l, r) = op(lhs, rhs)
    //down_f(l, r) = op(rhs, lhs)
    //で定義する
    template< typename T, typename Q1, typename Q2, typename F >
    T query2(int u, int v, const T &identity, const Q1 &up_f, const Q2 &down_f, const F &f, bool edge = false) {
        T sml = identity, smr = identity;
        do{
            if(leader[u] == leader[v]) break;
            if(ent[u] < ent[v]){
                smr = f( up_f(ent[leader[v]], ent[v] + 1), smr);
                v = par[leader[v]];
            }else{
                sml = f( sml, down_f(ent[leader[u]], ent[u] + 1));
                u = par[leader[u]];
            }
        }while(true);
        if(ent[u] < ent[v]){
            return f(sml,  f( up_f(ent[u] + edge, ent[v] + 1), smr));
        }else{
            return f(f(sml, down_f(ent[v] + edge, ent[u] + 1)), smr);
        }
    }
    //(頂点u, 頂点v, 列に対するupdate関数, 辺か頂点か)
    template< typename Q >
    void update(int u, int v, const Q &q, bool edge = false) {
        do{
            if(ent[u] > ent[v]) std::swap(u, v);
            if(leader[u] == leader[v]) break;
            q(ent[leader[v]], ent[v] + 1);
            v = par[leader[v]];
        }while(true);
        q(ent[u] + edge, ent[v] + 1);
    }
};

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int N, u, v, cmd, z;
    cin >> N;
    vector<pair<int,int>> a(N);
    vector<vector<int>> g(N);
    for(int i = 0; i < N; i++)cin >> a[i].first;
    for(int i = 0; i < N; i++)cin >> a[i].second;
    for(int i = 1; i < N; i++){
        cin >> u >> v;
        g[--u].push_back(--v);
        g[v].push_back(u);
    }
    Heavy_Light_Decomposition HLD(g);
    atcoder::lazy_segtree<S, op, e, F, mapping, composition, id> seg(N);
    for(int i = 0; i < N; i++){
        seg.set(HLD[i], make_pair(a[i].first, a[i].second));
    }
    auto f = [&](mint lhs, mint rhs){
        return lhs + rhs;
    };
    auto qf = [&](int l, int r){
        return seg.prod(l, r).first;
    };
    auto q = [&](int l, int r){
        seg.apply(l, r, z);
    };
    int Q;
    cin >> Q;
    while(Q--){
        cin >> cmd >> u >> v;
        u--, v--;
        if(cmd == 0){
            cin >> z;
            HLD.update(u, v, q);
        }else{
            cout << HLD.query(u, v, mint(0), qf, f).val() << '\n';
        }
    }
}
0