結果

問題 No.235 めぐるはめぐる (5)
ユーザー parukiparuki
提出日時 2016-08-18 15:33:04
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 1,147 ms / 10,000 ms
コード長 7,205 bytes
コンパイル時間 3,018 ms
コンパイル使用メモリ 194,000 KB
実行使用メモリ 25,856 KB
最終ジャッジ日時 2024-04-25 08:55:38
合計ジャッジ時間 8,216 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1,147 ms
24,960 KB
testcase_01 AC 724 ms
25,856 KB
testcase_02 AC 1,033 ms
25,088 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include "bits/stdc++.h"
using namespace std;
#define FOR(i,j,k) for(int (i)=(j);(i)<(int)(k);++(i))
#define rep(i,j) FOR(i,0,j)
#define each(x,y) for(auto &(x):(y))
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define debug(x) cout<<#x<<": "<<(x)<<endl
#define smax(x,y) (x)=max((x),(y))
#define smin(x,y) (x)=min((x),(y))
#define MEM(x,y) memset((x),(y),sizeof (x))
#define sz(x) (int)(x).size()
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<ll> vll;

template<int MOD>
class ModInt{
public:
    ModInt():value(0){}
    ModInt(long long val):value((int)(val<0?MOD+val%MOD:val%MOD)){ }

    ModInt& operator+=(ModInt that){
        value = value+that.value;
        if(value>=MOD)value-=MOD;
        return *this;
    }
    ModInt& operator-=(ModInt that){
        value -= that.value;
        if(value<0)value+=MOD;
        return *this;
    }
    ModInt& operator*=(ModInt that){
        value = (int)((long long)value * that.value % MOD);
        return *this;
    }
    ModInt &operator/=(ModInt that){
        return *this *= that.inverse();
    }
    ModInt operator+(ModInt that) const{
        return ModInt(*this)+=that;
    }
    ModInt operator-(ModInt that) const{
        return ModInt(*this)-=that;
    }
    ModInt operator*(ModInt that) const{
        return ModInt(*this)*=that;
    }
    ModInt operator/(ModInt that) const {
        return ModInt(*this) /= that;
    }
    ModInt operator^(long long k) const{
        if(value == 0)return 0;
        ModInt n = *this, res = 1;
        while(k){
            if(k & 1)res *= n;
            n *= n;
            k >>= 1;
        }
        return res;
    }
    ModInt inverse() const {
        long long a = value, b = MOD, u = 1, v = 0;
        while(b) {
            long long t = a / b;
            a -= t * b;
            swap(a, b);
            u -= t * v;
            swap(u, v);
        }
        return ModInt(u);
    }
    int toi() const{ return value; }

private:
    int value;
};
typedef ModInt<1000000007> mint;
ostream& operator<<(ostream& os, const mint& x){
    os << x.toi();
    return os;
}

struct HLDecomposition{
    vector<int> parent, depth, sub, id, head;
    int cur = 0;
    
    HLDecomposition(const vector<vector<int> > &G){
        parent = depth = sub = id = head = vector<int>(G.size());
        dfs(G, 0, -1, 0);
        dfs2(G, 0, -1, 0);
    }
    
    int dfs(const vector<vector<int> > &G, int u, int pre, int d){
        parent[u] = pre;
        sub[u] = 1;
        depth[u] = d;
        for(int v: G[u])
            if(v != pre)
                sub[u] += dfs(G, v, u, d+1);
        return sub[u];
    }

    void dfs2(const vector<vector<int> >&G, int u, int pre, int h){
        head[u] = h;
        id[u] = cur++;
        int heavy = -1, maxi = 0;
        for(int v : G[u]){
            if(v != pre && maxi < sub[v]){
                maxi = sub[v];
                heavy = v;
            }
        }
        
        if(heavy != -1)dfs2(G, heavy, u, h);

        for(int v : G[u]){
            if(v != pre&&v != heavy){
                dfs2(G, v, u, v);
            }
        }
    }

    vector<pair<int, int> > goUpToLCA(int u, int v){
        vector<pair<int, int> > res;
        while(true){
            if(head[u]==head[v]){
                if(depth[u] > depth[v])swap(u, v);
                res.emplace_back(id[u], id[v] + 1);
                break;
            } else{
                if(depth[head[u]] > depth[head[v]])swap(u, v);
                res.emplace_back(id[head[v]], id[v] + 1);
                v = parent[head[v]];
            }
        }
        return res;
    }
};

vector<mint> sumC;
bool init = true;

struct LazySegTreeSum{
    int dataSize;
    vector<mint> value, lazy;
    LazySegTreeSum(int n){
        dataSize = 1;
        while(dataSize < n)dataSize *= 2;
        int treeSize = 2 * dataSize;
        value = lazy = vector<mint>(treeSize);
    }

    void propagate(int index, int curL, int curR){
        // 自分の値をlazyにもとづいて書き換えて自分のlazyをクリア。
        if(lazy[index].toi()){
            int left = index * 2 + 1, right = index * 2 + 2;
            if(!init)value[index] += lazy[index] * (sumC[curR]-sumC[curL]);
            else value[index] += lazy[index] * (curR - curL);
            // 子のlazyを書き換える。
            if(curR - curL > 1){
                lazy[left] += lazy[index];
                lazy[right] += lazy[index];
            }
            lazy[index] = 0;
        }
    }

    // [curL, curR) を評価する
    void update(int index, int curL, int curR, int givenL, int givenR, int x){
        // 範囲外であろうとpropagateは必ず呼ぶ。そうでないと、親がうまく評価されない
        propagate(index, curL, curR);

        // 範囲外
        if(curR <= givenL || givenR <= curL)return;

        if(givenL <= curL && curR <= givenR){
            // 直接書き換えないでindexのlazyを書き換えてpropagateを呼ぶ
            lazy[index] += x;
            propagate(index, curL, curR);
        } else{
            int mid = (curL + curR) / 2;
            update(index * 2 + 1, curL, mid, givenL, givenR, x);
            update(index * 2 + 2, mid, curR, givenL, givenR, x);
            value[index] = value[index * 2 + 1] + value[index * 2 + 2];
        }
    }

    void update(int l, int r, int x){
        update(0, 0, dataSize, l, r, x);
    }

    mint query(int l, int r){
        return query(0, 0, dataSize, l, r);
    }

    mint query(int index, int curL, int curR, int givenL, int givenR){
        // 範囲外
        if(curR <= givenL || givenR <= curL)return 0;

        propagate(index, curL, curR);

        if(givenL <= curL && curR <= givenR){
            return value[index];
        } else{
            int mid = (curL + curR) / 2;
            mint resL = query(index * 2 + 1, curL, mid, givenL, givenR);
            mint resR = query(index * 2 + 2, mid, curR, givenL, givenR);
            return resL + resR;
        }
    }
};

int main(){

    int N;
    cin >> N;
    vi S(N), C(N);
    rep(i, N)scanf("%d", &S[i]);
    rep(i, N)scanf("%d", &C[i]);

    vector<vi> G(N);
    rep(i, N-1){
        int a, b;
        scanf("%d%d", &a, &b);
        --a; --b;
        G[a].push_back(b);
        G[b].push_back(a);
    }

    auto hlc = HLDecomposition(G);
    LazySegTreeSum st(N);
    int M = st.dataSize;
    sumC = vector<mint>(M+1);
    rep(i, N){
        int u = hlc.id[i];
        st.update(u, u + 1, S[i]);
        sumC[u+1] = C[i];
    }
    rep(i, M)sumC[i + 1] += sumC[i];
    init = false;

    int Q;
    cin >> Q;
    while(Q--){
        int q, x, y;
        scanf("%d%d%d", &q, &x, &y);
        --x;
        --y;
        if(q == 0){
            int z;
            scanf("%d", &z);

            auto segs = hlc.goUpToLCA(x, y);
            each(seg, segs){
                st.update(seg.first, seg.second, z);
            }
        } else{
            mint ans;
            auto segs = hlc.goUpToLCA(x, y);
            each(seg, segs){
                ans += st.query(seg.first, seg.second);
            }
            printf("%d\n", ans.toi());
        }
    }
}
0