結果

問題 No.235 めぐるはめぐる (5)
ユーザー pekempeypekempey
提出日時 2016-12-06 07:22:14
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 252 ms / 10,000 ms
コード長 5,047 bytes
コンパイル時間 5,527 ms
コンパイル使用メモリ 191,484 KB
実行使用メモリ 25,948 KB
最終ジャッジ日時 2023-08-18 18:28:09
合計ジャッジ時間 6,785 ms
ジャッジサーバーID
（参考情報） 		judge11 / judge12
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 252 ms
25,040 KB
testcase_01 AC 171 ms
25,948 KB
testcase_02 AC 229 ms
25,252 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');
}

const int mod = 1e9 + 7;

int add(int a, int b) {
    return (a += b) >= mod ? a - mod : a;
}

int sub(int a, int b) {
    return add(a, mod - b);
}

int mul(int a, int b) {
    return 1LL * a * b % mod;
}

const int N = 2e5 + 10;

struct Node {
    int64_t sum0 = 0;
    int64_t sum1 = 0;
};

Node nodes[N];
int w[N + 1];
int64_t ss[N + 1];
int offset;
int size;

void addPoint(int k, int64_t v0, int64_t v1) {
    Node *ft = nodes + offset;
    v0 %= mod;
    v1 %= mod;
    k -= offset;
    k++;
    while (k <= size) {
        ft[k].sum0 += v0;
        ft[k].sum1 += v1;
        k += k & -k;
    }
}

int64_t sum(int k) {
    Node *ft = nodes + offset;
    k++;
    int x = k;
    k -= offset;
    int64_t res0 = 0;
    int64_t res1 = 0;
    while (k > 0) {
        res0 += ft[k].sum0;
        res1 += ft[k].sum1;
        k &= k - 1;
    }
    res1 %= mod;
    return (res0 + res1 * sub(w[x], w[offset])) % mod;
}

int sum(int l, int r) {
    return sub(sum(r - 1), sum(l - 1));
}

void add(int l, int r, int value) {
    addPoint(l, 1LL * (mod - value) * sub(w[l], w[offset]), value);
    addPoint(r, 1LL * value * sub(w[r], w[offset]), mod - value);
}

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

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

    vector<Node> nodes;

    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, int)> f) {
        while (true) {
            if (nodes[u].vid > nodes[v].vid) {
                swap(u, v);
            }
            int h = nodes[v].head;
            int l = nodes[h].length;
            if (nodes[u].head == nodes[v].head) {
                f(nodes[h].vid, l, nodes[u].vid, nodes[v].vid);
                break;
            } else {
                f(nodes[h].vid, l, nodes[h].vid, nodes[v].vid);
                v = nodes[h].parent;
            }
        }
    }

    int operator[](int k) {
        return nodes[k].vid;
    }

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);
        int k = 0;
        while (!q.empty()) {
            int h = q.front();
            q.pop();
            for (int i = h; i != -1; i = nodes[i].heavy) {
                nodes[i].vid = k++;
                nodes[i].head = h;
                nodes[h].length++;
                for (int j : g[i]) {
                    if (j != nodes[i].parent && j != nodes[i].heavy) {
                        q.push(j);
                    }
                }
            }
        }
    }
};

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);
    for (int i = 0; i < n; i++) {
        ss[hld[i] + 1] = s[i];
        w[hld[i] + 1] = c[i];
    }
    for (int i = 1; i < N; i++) {
        ss[i] += ss[i - 1];
        w[i] = add(w[i], w[i - 1]);
    }
    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 head, int len, int l, int r) {
                offset = head;
                size = len;
                add(l, r + 1, z);
            });
        } else {
            int u = in() - 1;
            int v = in() - 1;
            int64_t ans = 0;
            hld.forEach(u, v, [&](int head, int len, int l, int r) {
                offset = head;
                size = len;
                ans += sum(l, r + 1);
                ans += ss[r + 1] - ss[l];
            });
            putInt(ans % mod);
        }
    }
}
0