#48092 (C++11) No.235 めぐるはめぐる (5)

• 問題: No.235 めぐるはめぐる (5)
• ユーザー: pekempey
• 提出日時: 2015-09-06 13:04:12
• 言語: C++11 (gcc 11.4.0)
• 結果: AC
• 実行時間: 1,715 ms / 10,000 ms
• コード長: 10,065 bytes
• コンパイル時間: 2,037 ms
• コンパイル使用メモリ: 188,640 KB
• 実行使用メモリ: 108,120 KB
• 最終ジャッジ日時: 2024-07-19 04:23:29
• 合計ジャッジ時間: 9,182 ms
• ジャッジサーバーID （参考情報）: judge3 / judge4

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	1,715 ms; 98,024 KB
testcase_01	AC	1,355 ms; 108,120 KB
testcase_02	AC	1,653 ms; 100,292 KB

ソースコード

#include <bits/stdc++.h>
#define rep(i, a) for (int i = 0; i < (a); i++)
#define rep2(i, a, b) for (int i = (a); i < (b); i++)
#define repr(i, a) for (int i = (a) - 1; i >= 0; i--)
#define repr2(i, a, b) for (int i = (b) - 1; i >= (a); i--)
using namespace std;
typedef long long ll;

const int inf = 1e9;
const ll mod = 1e9 + 7;

struct F {
	ll x;
	F() : x(0) {}
	F(ll x) { this->x = modulo(x); }
	static ll modulo(ll a) {
		a %= mod; a += mod; a %= mod; 
		return a;
	}
	static ll modpow(ll a, ll b) {
		if (b == 0) return 1;
		return modpow(a * a % mod, b / 2) * (b & 1 ? a : 1) % mod;
	}
	static ll modinv(ll a) {
		return modpow(a, mod - 2);
	}
	F operator +(F b) { return F(x + b.x); }
	F operator +(ll b) { return F(x + b); }
	F &operator +=(F b) { x = modulo(x + b.x); return *this; }
	F &operator +=(ll b) { x = modulo(x + b); return *this; }
	F operator -(F b) { return F(x - b.x); }
	F operator -(ll b) { return F(x - b); }
	F &operator -=(F b) { x = modulo(x - b.x); return *this; }
	F &operator -=(ll b) { x = modulo(x - b); return *this; }
	F operator *(F b) { return F(x * b.x); }
	F operator *(ll b) { return F(x * b); }
	F &operator *=(F b) { x = modulo(x * b.x); return *this; }
	F &operator *=(ll b) { x = modulo(x * b); return *this; }
	F operator /(F b) { return F(x * modinv(b.x)); }
	F operator /(ll b) { return F(x * modinv(b)); }
	F &operator /=(F b) { x = modulo(x * modinv(b.x)); return *this; }
	F &operator /=(ll b) { x = modulo(x * modinv(b)); return *this; }
	F &operator =(ll b) { x = modulo(b); return *this; }
	operator int() { return x; }
	operator long long() { return x; }
	friend ostream &operator <<(ostream &os, F a) { os << a.x; return os; }
	friend istream &operator >>(istream &is, F &a) { is >> a.x; a.x = modulo(a.x); return is; }
};

template<class T>
struct RMQ {
    vector<T> seg;
    int size;
    T inf;
    RMQ(int n, T inf) {
        this->inf = inf;
        size = 1;
        while (size < n) size *= 2;
        seg.resize(size * 2 - 1, inf);
    }
    void update(int k, T x) {
        k += size - 1;
        seg[k] = x;
        while (k > 0) {
            k = (k - 1) / 2;
            seg[k] = min(seg[k * 2 + 1], seg[k * 2 + 2]);
        }
    }
    T query(int a, int b, int k, int l, int r) {
        if (r <= a || b <= l) return inf;
        if (a <= l && r <= b) return seg[k];
        T vl = query(a, b, k * 2 + 1, l, (l + r) / 2);
        T vr = query(a, b, k * 2 + 2, (l + r) / 2, r);
        return min(vl, vr);
    }
    T query(int a, int b) {
        return query(a, b, 0, 0, size);
    }
};

struct LCA {
    RMQ<pair<int, int>> rmq;
    vector<pair<int, int> > euler;
    vector<vector<int> > G;
    vector<int> id;
    int root;
    LCA(int V) : rmq(V * 2 - 1, make_pair(inf, inf)), G(V), id(V), euler(V * 2 - 1) {}
    void add(int u, int v) {
        G[u].push_back(v);
        G[v].push_back(u);
    }
    void dfs(int curr, int prev, int depth, int &k) {
        id[curr] = k;
        euler[k++] = make_pair(depth, curr);
        for (int next : G[curr]) if (next != prev) {
            dfs(next, curr, depth + 1, k);
            euler[k++] = make_pair(depth, curr);
        }
    }
    void build(int root = 0) {
        this->root = root;
        int k = 0;
        dfs(root, -1, 0, k);
        rep (i, euler.size()) {
            rmq.update(i, euler[i]);
        }
    }
    int query(int u, int v) {
        return rmq.query(min(id[u], id[v]), max(id[u], id[v]) + 1).second;
    }
};

struct HL {
    vector<vector<int>> G, color, path;
    vector<int> parent, head, order, size, heads;
    int root;
    HL(int n) : G(n), color(n), parent(n), head(n), order(n), size(n), path(n) {}
    void add(int u, int v) {
        G[u].push_back(v);
        G[v].push_back(u);
    }
    int dfs(int curr, int prev) {
        int res = 1;
        parent[curr] = prev;
        rep (i, G[curr].size()) {
            int next = G[curr][i];
            if (next == prev) continue;
            int d = dfs(next, curr);
            color[curr][i] = d;
            res += d;
        }
        int maxi = max_element(color[curr].begin(), color[curr].end()) - color[curr].begin();
        rep (i, G[curr].size()) {
            color[curr][i] = maxi == i;
        }
        return res;
    }
    void dfs2(int curr, int prev) {
        rep (i, G[curr].size()) {
            int next = G[curr][i];
            if (next == prev) continue;
            if (color[curr][i]) {
                head[next] = head[curr];
                order[next] = order[curr] + 1;  
            }
            dfs2(next, curr);
        } 
    }
    void build(int root = 0) {
        this->root = root;
        int V = G.size();
        rep (i, V) color[i].resize(G[i].size());
        dfs(root, -1);
        rep (i, V) head[i] = i;
        dfs2(root, -1);
        rep (i, V) size[head[i]]++;
        rep (i, V) {
            if (i == head[i]) {
                heads.push_back(i);
                path[i].resize(size[i]);
            }
        }
        rep (i, V) {
            path[head[i]][order[i]] = i;
        }
    }
    int skip(int v) {
        return parent[head[v]];
    }
    int vid(int h, int ord) {
        return path[h][ord];
    }
};	

struct HLIterator {
    int u, v, l;
    HL *hl;
    LCA *lca;
    HLIterator(HL *hl, int u) : hl(hl), u(u), v(0), l(hl->root) {}
    HLIterator(HL *hl, LCA *lca, int u, int v) : hl(hl), lca(lca), u(u), v(v) {
        l = lca->query(u, v);
    }
    // head, [from, to)
    tuple<int, int, int> next() {
        if (hl->head[l] != hl->head[u]) {
            int pu = u;
            u = hl->skip(u);
            return make_tuple(hl->head[pu], 0, hl->order[pu] + 1);
        }
        if (hl->head[l] != hl->head[v]) {
            int pv = v;
            v = hl->skip(v);
            return make_tuple(hl->head[pv], 0, hl->order[pv] + 1);
        }
        int a = min(hl->order[u], hl->order[v]);
        int b = max(hl->order[u], hl->order[v]);
        u = -1; v = -1;
        return make_tuple(hl->head[l], a, b + 1);
    }
    bool has_next() {
        return u != -1 && v != -1;
    }
};

ll modulo(ll a) {
    a %= mod; a += mod; a %= mod;
    return a;
}

struct SegmentTree {
    vector<F> seg, lazy, weight, wsum;
    int size;
    void init(int n) {
        size = 1;
        while (size < n) size *= 2;
        seg.resize(size * 2);
        lazy.resize(size * 2);
        weight.resize(size);
    }
    void set_value(int k, F v) {
        seg[k + size - 1] = v;
    }
    void set_weight(int k, F w) {
        weight[k] = w;
    }
    void build() {
        wsum.resize(size + 1);	
        rep (i, size) {
            wsum[i + 1] += wsum[i] + weight[i];
        }
        repr (i, size - 1) {
            seg[i] = seg[i * 2 + 1] + seg[i * 2 + 2];
        }
    }
    void evallazy(int k, int l, int r) {
        seg[k] += lazy[k] * (wsum[r] - wsum[l]);
        if (r - l > 1) {
            lazy[k * 2 + 1] += lazy[k];
            lazy[k * 2 + 2] += lazy[k];
        }
        lazy[k] = 0;
    }
    void update(int a, int b, F v, int k, int l, int r) {
        evallazy(k, l, r);
        if (r <= a || b <= l) return;
        if (a <= l && r <= b) {
            lazy[k] = v;
            evallazy(k, l, r);
        } else {
            update(a, b, v, k * 2 + 1, l, (l + r) / 2);
            update(a, b, v, k * 2 + 2, (l + r) / 2, r);
            seg[k] = seg[k * 2 + 1] + seg[k * 2 + 2];
        }
    }
    void update(int a, int b, F v) {
        update(a, b, v, 0, 0, size);
    }
    F query(int a, int b, int k, int l, int r) {
        evallazy(k, l, r);
        if (r <= a || b <= l) return 0;
        if (a <= l && r <= b) return seg[k];
        F res = 0;
        res += query(a, b, k * 2 + 1, l, (l + r) / 2);
        res += query(a, b, k * 2 + 2, (l + r) / 2, r);
        return res;
    }
    F query(int a, int b) {
        return query(a, b, 0, 0, size);
    }
};

SegmentTree seg[202020];

void update(HL &hl, LCA &lca, int x, int y, int z) {
    HLIterator it(&hl, &lca, x, y);
    while (it.has_next()) {
        auto t = it.next();
        int head = get<0>(t);
        int l = get<1>(t);
        int r = get<2>(t);
        seg[head].update(l, r, z);
    }
}

F query(HL &hl, LCA &lca, int x, int y) {
    HLIterator it(&hl, &lca, x, y);
    F res = 0;
    while (it.has_next()) {
        auto t = it.next();
        int head = get<0>(t);
        int l = get<1>(t);
        int r = get<2>(t);
        res += seg[head].query(l, r);
    }
    return res;
}

struct Stopwatch {
    double begin;
    Stopwatch() {
        start();
    }
    void start() {
        begin = clock();
    }
    double elapsed() {
        double end = clock();
        double res = (double)(end - begin) / CLOCKS_PER_SEC * 1000.0;
        begin = end;
        return res;
    }
    void display(string text) {
        cerr << text << ":" << elapsed() << "ms" << endl;
    }
};

int main() {
    Stopwatch whole;
    int N;
    cin >> N;
    vector<int> S(N), C(N);
    rep (i, N) cin >> S[i];
    rep (i, N) cin >> C[i];
    HL hl(N);
    LCA lca(N);
    rep (i, N - 1) {
        int a, b;
        cin >> a >> b;
        a--; b--;
        hl.add(a, b);
        lca.add(a, b);
    }
    Stopwatch sw;
    hl.build();
    sw.display("build HL");
    lca.build();
    sw.display("build LCA");
    for (int h : hl.heads) {
        seg[h].init(hl.size[h]);
    }
    sw.display("init SegmentTree");
    rep (i, N) {
        seg[hl.head[i]].set_value(hl.order[i], S[i]);
        seg[hl.head[i]].set_weight(hl.order[i], C[i]);
    }
    for (int h : hl.heads) {
        seg[h].build();	
    }
    sw.display("build SegmentTree");
    int Q;
    cin >> Q;
    while (Q--) {
        int q;
        cin >> q;
        if (q == 0) {
            int x, y, z;
            cin >> x >> y >> z;
            x--; y--;
            update(hl, lca, x, y, z);
        } else {
            int x, y;
            cin >> x >> y;
            x--; y--;
            F ans = query(hl, lca, x, y);
            cout << ans << "\n";
        }
    }
    sw.display("query");
    whole.display("whole");
}