結果

問題 No.235 めぐるはめぐる (5)
ユーザー pekempeypekempey
提出日時 2016-12-06 06:31:39
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 444 ms / 10,000 ms
コード長 7,005 bytes
コンパイル時間 3,881 ms
コンパイル使用メモリ 210,428 KB
実行使用メモリ 60,168 KB
最終ジャッジ日時 2024-05-06 00:12:51
合計ジャッジ時間 7,577 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 419 ms
40,612 KB
testcase_01 AC 408 ms
60,168 KB
testcase_02 AC 444 ms
42,472 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#pragma GCC optimize ("O3")
#pragma GCC target ("avx")
#include <bits/stdc++.h>
using namespace std;

#define getchar getchar_unlocked
#define putchar putchar_unlocked

int in() {
    int n, c;
    while ((c = getchar()) < '0') if (c == EOF) return -1;
    n = c - '0';
    while ((c = getchar()) >= '0') n = n * 10 + c - '0';
    return n;
}

void putInt(int n) {
    int res[11], i = 0;
    do { res[i++] = n % 10, n /= 10; } while (n);
    while (i) putchar(res[--i] + '0');
    putchar('\n');
}

template<class T>
class WeightedFenwickTree {
private:
    struct Node {
        T sum0 = 0;
        T sum1 = 0;
    };

private:
    vector<Node> nodes;
    vector<T> sumWeight;

public:
    WeightedFenwickTree(vector<T> weights) {
        const int n = weights.size();
        nodes.resize(n + 1);
        sumWeight.resize(n + 1);
        for (int i = 0; i < n; i++) {
            sumWeight[i + 1] = sumWeight[i] + weights[i];
        }
    }

    WeightedFenwickTree(vector<T> weights, vector<T> values) {
        const int n = weights.size();
        nodes.resize(n + 1);
        sumWeight.resize(n + 1);
        for (int i = 0; i < n; i++) {
            nodes[i + 1].sum0 = values[i] * weights[i];
            sumWeight[i + 1] = sumWeight[i] + weights[i];
        }
        for (int i = 1; i <= n; i++) {
            if (i + (i & -i) <= n) {
                nodes[i + (i & -i)].sum0 += nodes[i].sum0;
            }
        }
    }

private:
    void addPoint(int k, T v0, T v1) {
        k++;
        while (k < nodes.size()) {
            nodes[k].sum0 += v0;
            nodes[k].sum1 += v1;
            k += k & -k;
        }
    }

    T sum(int k) {
        k++;
        T res0 = 0;
        T res1 = 0;
        int x = k;
        while (k > 0) {
            res0 += nodes[k].sum0;
            res1 += nodes[k].sum1;
            k -= k & -k;
        }
        return res0 + res1 * sumWeight[x];
    }

public:
    T sum(int l, int r) {
        return sum(r - 1) - sum(l - 1);
    }

    void add(int l, int r, T value) {
        addPoint(l, -value * sumWeight[l], +value);
        addPoint(r, +value * sumWeight[r], -value);
    }
};

template<class T>
class CumulativeSum {
private:
    vector<T> s;
    
public:
    CumulativeSum(vector<T> a) : s(a.size() + 1) {
        for (int i = 0; i < a.size(); i++) {
            s[i + 1] = s[i] + a[i];
        }
    }

    T sum(int l, int r) {
        return s[r] - s[l];
    }
};

struct ModInt {
    static const int mod = 1e9 + 7;
    int n;

    ModInt() : n(0) {}

    ModInt(int n) : n(n) {}

    int intValue() {
        return n;
    }

    ModInt operator+() const {
        return *this;
    }

    ModInt operator-() const {
        return ModInt(n == 0 ? 0 : mod - n);
    }

    ModInt &operator+=(const ModInt &r) {
        if ((n += r.n) >= mod) {
            n -= mod;
        }
        return *this;
    }

    ModInt operator+(const ModInt &r) const {
        ModInt res;
        res.n = n + r.n;
        if (res.n >= mod) {
            res.n -= mod;
        }
        return res;
    }

    ModInt &operator-=(const ModInt &r) {
        *this += -r;
        return *this;
    }

    ModInt operator-(const ModInt &r) const {
        return *this + (-r);
    }

    ModInt &operator*=(const ModInt &r) {
        n = 1LL * n * r.n % mod;
        return *this;
    }

    ModInt operator*(const ModInt &r) const {
        return ModInt(1LL * n * r.n % mod);
    }
};

class HeavyLightDecomposition {
private:
    const vector<vector<int>> &g;

public:
    struct Node {
        int vid;
        int hid;
        int head;
        int parent;
        int heavy;
    };

    vector<Node> nodes;
    vector<vector<int>> paths;

    HeavyLightDecomposition(const vector<vector<int>> &g) : g(g), nodes(g.size()) {
        dfs(0, -1);
        bfs(0);
    }

    void forEach(int u, int v, function<void(int, int, int)> f) {
        while (true) {
            if (nodes[u].head == nodes[v].head) {
                if (nodes[u].vid > nodes[v].vid) {
                    swap(u, v);
                }
                f(nodes[u].hid, nodes[u].vid, nodes[v].vid);
                break;
            } else {
                if (nodes[u].hid < nodes[v].hid) {
                    swap(u, v);
                }
                f(nodes[u].hid, nodes[nodes[u].head].vid, nodes[u].vid);
                u = nodes[nodes[u].head].parent;
            }
        }
    }

private:
    int dfs(int curr, int prev) {
        nodes[curr].heavy = -1;
        nodes[curr].parent = prev;
        int maxSub = 0;
        int sub = 1;
        for (int next : g[curr]) {
            if (next == prev) {
                continue;
            }
            int subNext = dfs(next, curr);
            sub += subNext;
            if (maxSub < subNext) {
                maxSub = subNext;
                nodes[curr].heavy = next;
            }
        }
        return sub;
    }

    void bfs(int s) {
        queue<int> q;
        q.push(s);
        while (!q.empty()) {
            int h = q.front();
            q.pop();
            vector<int> path;
            for (int i = h; i != -1; i = nodes[i].heavy) {
                nodes[i].vid = path.size();
                nodes[i].hid = paths.size();
                nodes[i].head = h;
                path.push_back(i);
                for (int j : g[i]) {
                    if (j != nodes[i].parent && j != nodes[i].heavy) {
                        q.push(j);
                    }
                }
            }
            paths.emplace_back(path);
        }
    }
};

int main() {
    int n;
    cin >> n;
    vector<int> s(n);
    vector<int> c(n);
    for (int i = 0; i < n; i++) {
        s[i] = in();
    }
    for (int i = 0; i < n; i++) {
        c[i] = in();
    }
    vector<vector<int>> g(n);
    for (int i = 0; i < n - 1; i++) {
        int a = in() - 1;
        int b = in() - 1;
        g[a].push_back(b);
        g[b].push_back(a);
    }
    HeavyLightDecomposition hld(g);
    vector<WeightedFenwickTree<ModInt>> ft;
    vector<CumulativeSum<ModInt>> csum;
    for (auto path : hld.paths) {
        vector<ModInt> ss(path.size());
        vector<ModInt> cc(path.size());
        for (int i = 0; i < path.size(); i++) {
            ss[i] = s[path[i]];
            cc[i] = c[path[i]];
        }
        csum.emplace_back(ss);
        ft.emplace_back(cc);
    }
    int q;
    cin >> q;
    for (int i = 0; i < q; i++) {
        int t;
        t = in();
        if (t == 0) {
            int u = in() - 1;
            int v = in() - 1;
            int z = in();
            hld.forEach(u, v, [&](int h, int l, int r) {
                ft[h].add(l, r + 1, z);
            });
        } else {
            int u = in() - 1;
            int v = in() - 1;
            ModInt ans = 0;
            hld.forEach(u, v, [&](int h, int l, int r) {
                ans += ft[h].sum(l, r + 1);
                ans += csum[h].sum(l, r + 1);
            });
            putInt(ans.intValue());
        }
    }
}
0