#110187 (C++14) No.235 めぐるはめぐる (5)

• 問題: No.235 めぐるはめぐる (5)
• ユーザー: paruki
• 提出日時: 2016-08-12 21:09:20
• 言語: C++14 (gcc 12.3.0 + boost 1.83.0)
• 結果: WA
• 実行時間: -
• コード長: 11,150 bytes
• コンパイル時間: 2,804 ms
• コンパイル使用メモリ: 205,976 KB
• 実行使用メモリ: 81,000 KB
• 最終ジャッジ日時: 2024-11-07 12:16:38
• 合計ジャッジ時間: 9,235 ms
• ジャッジサーバーID （参考情報）: judge3 / judge4

入力	結果	実行時間; 実行使用メモリ
testcase_00	WA	-
testcase_01	WA	-
testcase_02	WA	-

ソースコード

#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;

class LCA{
public:
    LCA(){ }
    LCA(const vector<vector<int>> &G, int root = 0):V((int)G.size()), depth(V), parent(V){
        rep(i, LG)ancestor[i] = vector<int>(V);
        dfs(root, 0, 0, G);
        rep(i, V)
            ancestor[0][i] = parent[i];
        rep(i,LG-1)rep(v,V)
            ancestor[i + 1][v] = ancestor[i][ancestor[i][v]];
    }
    int get(int u, int v){
        if(depth[u] < depth[v]) swap(u, v);
        int dist = depth[u] - depth[v];
        for(int i = 0; i < LG; ++i)
            if((dist >> i) & 1)
                u = ancestor[i][u];
        if(u == v) return u;
        for(int i = LG - 1; i >= 0; --i){
            if(ancestor[i][u] != ancestor[i][v]){
                u = ancestor[i][u];
                v = ancestor[i][v];
            }
        }
        return ancestor[0][u];
    }
    int getDepth(int u){
        return depth[u];
    }
    int goUp(int u, int len){
        for(int i = 0; i < LG; ++i)
            if(len >> i & 1)u = ancestor[i][u];
        return u;
    }
    int distance(int u, int v){
        return depth[u] + depth[v] - 2 * depth[get(u, v)];
    }
    int getParent(int u){
        return parent[u];
    }
    static const int LG = 18;
private:
    int V;
    vector<int> depth, parent, ancestor[LG];
    void dfs(int v, int p, int d, const vector<vector<int>> &G){
        depth[v] = d;
        parent[v] = p;
        for(int to : G[v]){
            if(to != p){
                dfs(to, v, d + 1, G);
            }
        }
    }
};

struct HLDecomposition{
    vector<int> subtreeSize, parent, group, idInPath;
    vector<vector<int>> paths;

    HLDecomposition(){ }

    HLDecomposition(const vector<vector<int>> &G){
        subtreeSize = parent = group = idInPath = vector<int>(G.size(), 1);
        dfs1(G, 0, -1);
        paths.push_back(vector<int>());
        dfs2(G, 0, -1, 0);
    }

    int dfs1(const vector<vector<int>> &G, int u, int pre){
        parent[u] = pre;
        int &res = subtreeSize[u];
        for(int v : G[u]){
            if(v != pre){
                res += dfs1(G, v, u);
            }
        }
        return res;
    }

    void dfs2(const vector<vector<int>> &G, int u, int pre, int pathId){
        idInPath[u] = (int)paths[pathId].size();
        paths[pathId].push_back(u);
        group[u] = pathId;
        int heavy = -1, maxSize = 0;
        for(int v : G[u]){
            if(v != pre && subtreeSize[v] > maxSize){
                heavy = v;
                maxSize = subtreeSize[v];
            }
        }

        if(heavy != -1){
            dfs2(G, heavy, u, pathId);
        }

        for(int v : G[u]){
            if(v != pre && v != heavy){
                paths.push_back(vector<int>());
                dfs2(G, v, u, (int)paths.size() - 1);
            }
        }
    }

    /*
    頂点uから根まで登って、その途上にあるパスのIDとそのパスの通過箇所の右端を求める。
    */
    vector<pair<int, int> > goToRoot(int u){
        vector<pair<int, int> > res;
        while(group[u] != group[0]){
            res.emplace_back(group[u], idInPath[u] + 1);
            u = parent[paths[group[u]][0]];
        }
        res.emplace_back(0, idInPath[u] + 1);
        return res;
    }
};

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;
}

// sumC[i][j] // i番目のpathの[0, j)までの和
vector<vector<mint>> sumC;
int currentSegTree = 0;
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){
        vector<mint> &curSumC = sumC[currentSegTree];

        // 自分の値をlazyにもとづいて書き換えて自分のlazyをクリア。
        if(lazy[index].toi()){
            int left = index * 2, right = index * 2 + 1;
            if(!init){
                value[index] += lazy[index] * (curSumC[curR] - curSumC[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, curL, mid, givenL, givenR, x);
            update(index * 2 + 1, mid, curR, givenL, givenR, x);
            value[index] = value[index * 2] + value[index * 2 + 1];
        }
    }

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

    mint query(int l, int r){
        return query(1, 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, curL, mid, givenL, givenR);
            mint resR = query(index * 2 + 1, mid, curR, givenL, givenR);
            return resL + resR;
        }
    }
};

int main(){
    int N;
    cin >> N;
    vector<vi> G(N);
    vector<LazySegTreeSum> segtree;
    HLDecomposition hld;
    LCA lca;

    // 前処理
    {
        vi S(N), C(N);
        rep(i, N)scanf("%d", &S[i]);
        rep(i, N)scanf("%d", &C[i]);
        rep(i, N - 1){
            int A, B;
            scanf("%d%d", &A, &B);
            --A; --B;
            G[A].push_back(B);
            G[B].push_back(A);
        }

        hld = HLDecomposition(G);
        lca = LCA(G);
    
        each(path, hld.paths){
            segtree.push_back(LazySegTreeSum(sz(path)));

            sumC.push_back(vector<mint>(sz(path) + 1));

            // とりあえず初期値のSを入れておく
            rep(i, sz(path)){
                segtree.back().update(i, i + 1, S[path[i]]);
                sumC.back()[i + 1] = sumC.back()[i] + C[path[i]];
            }

            vector<mint> &curSumC = sumC.back();
            for(int i = 0; i <= 30; ++i){
                while(sz(curSumC) < (1 << i)){
                    curSumC.push_back(curSumC.back());
                }
                if(sz(curSumC) == 1 << i)break;
            }
            rep(i, 10)curSumC.push_back(curSumC.back());
        }

        init = false;
    }

    // HL分解のテスト
    //{
    //    rep(i, N){
    //        debug(i + 1);
    //        auto test = hld.goToRoot(i);
    //        each(p, test){
    //            debug(p.first);
    //            debug(p.second);
    //        }
    //    }
    //}


    // クエリ処理
    {
        int Q;
        cin >> Q;
        while(Q--){
            int q, X, Y;
            scanf("%d%d%d", &q, &X, &Y);
            --X; --Y;
            int l = lca.get(X, Y);

            if(q == 0){
                // パレード
                int Z;
                scanf("%d", &Z);
                for(int u : {X, Y}){
                    auto segs = hld.goToRoot(u);
                    each(seg, segs){
                        currentSegTree = seg.first;
                        segtree[currentSegTree].update(0, seg.second, Z);
                    }
                }

                auto segs = hld.goToRoot(l);
                each(seg, segs){
                    currentSegTree = seg.first;
                    segtree[currentSegTree].update(0, seg.second, -2ll*Z);
                }
                segtree[hld.group[l]].update(hld.idInPath[l], hld.idInPath[l] + 1, Z);
            } else{
                mint ans = 0;
                // めぐるの旅行
                for(int u : {X, Y}){
                    auto segs = hld.goToRoot(u);
                    each(seg, segs){
                        currentSegTree = seg.first;
                        ans += segtree[currentSegTree].query(0, seg.second);
                    }
                }

                auto segs = hld.goToRoot(l);
                each(seg, segs){
                    currentSegTree = seg.first;
                    ans -= segtree[currentSegTree].query(0, seg.second) * 2;
                }
                ans += segtree[hld.group[l]].query(hld.idInPath[l], hld.idInPath[l] + 1);

                printf("%d\n", ans.toi());
            }
        }
    }
}