結果

問題 No.235 めぐるはめぐる (5)
コンテスト
ユーザー shisidor
提出日時 2025-05-01 12:28:29
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 4,866 bytes
コンパイル時間 4,218 ms
コンパイル使用メモリ 295,112 KB
実行使用メモリ 34,832 KB
最終ジャッジ日時 2025-05-01 12:28:47
合計ジャッジ時間 16,617 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other WA * 3
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const ll mod = 1e9 + 7;

vector<vector<int>> G;
int sizesubtree[200009], par[200009], fir[200009], idx[200009];
vector<int> tour = {0};
vector<ll> ss, cc;

void dfs1(int now, int pre = -1) {
    //cout << "dfs1 " << now << " " << pre << endl;
    sizesubtree[now] = 1;
    for (int &nex : G[now]) {
        if (nex == pre) continue;
        par[nex] = now;
        dfs1(nex, now);
        sizesubtree[now] += sizesubtree[nex];
        if (sizesubtree[nex] > sizesubtree[G[now][0]] || G[now][0] == pre) swap(nex, G[now][0]);
    }
}

void dfs2(int now, int a, int pre = -1) {
    //cout << "dfs2 " << now << " " << a << " " << pre << endl;
    fir[now] = a;
    idx[now] = tour.size();
    tour.push_back(now);
    for (int i = 0; i < (int)G[now].size(); i++) {
        if (G[now][i] == pre) continue;
        if (i == 0) dfs2(G[now][0], a, now);
        else dfs2(G[now][i], G[now][i], now);
    }
}

ll inv(ll a) {
    ll b = mod, u = 1, v = 0;
    a %= mod; if (a < 0) a += mod;
    while (b) {
        ll t = a / b;
        a -= b * t; swap(a, b);
        u -= v * t; swap(u, v);
    }
    u %= mod;
    if (u < 0) u += mod;
    return u;
}

struct LazySegmentTree {
    int siz = 1;
    vector<ll> node, lazy;

    LazySegmentTree(vector<ll> vec) {
        int n = vec.size();
        while (siz < n) siz *= 2;
        node.assign(siz * 2, 0); lazy.assign(siz * 2, 0);
        for (int i = 1; i < n; i++) node[i + siz - 1] = vec[i] % mod;
        for (int i = siz - 1; i >= 1; i--) node[i] = (node[i * 2] + node[i * 2 + 1]) % mod;
    }

    void eval(int a, int b, int u) {
        if (lazy[u] != 0) {
            lazy[u] %= mod;
            node[u] += lazy[u]; node[u] %= mod;
            if (b - a > 1) {
                int m = (a + b) / 2;
                lazy[u * 2] += lazy[u] * inv(cc[b - 1] - cc[a - 1]) % mod * (cc[m - 1] - cc[a - 1]) % mod;
                lazy[u * 2 + 1] += lazy[u] * inv(cc[b - 1] - cc[a - 1]) % mod * (cc[b - 1] - cc[m - 1]) % mod;
                lazy[u * 2] %= mod; lazy[u * 2 + 1] %= mod;
            }
            lazy[u] = 0;
        }
    }

    void add(int l, int r, int a, int b, int u, ll x) {
        if (r <= a || b <= l) return;
        eval(a, b, u);
        if (l <= a && b <= r) {
            lazy[u] += x * (cc[b - 1] - cc[a - 1]) % mod;
            eval(a, b, u);
            return;
        }
        int m = (a + b) / 2;
        add(l, r, a, m, u * 2, x); add(l, r, m, b, u * 2 + 1, x);
        node[u] = (node[u * 2] + node[u * 2 + 1]) % mod;
    }

    ll Query(int l, int r, int a, int b, int u) {
        if (r <= a || b <= l) return 0;
        eval(a, b, u);
        if (l <= a && b <= r) return node[u] % mod;
        int m = (a + b) / 2;
        return (Query(l, r, a, m, u * 2) + Query(l, r, m, b, u * 2 + 1)) % mod;
    }
};

template<class T> void print(vector<T> a) {
    int n = a.size();
    for (int i = 0; i < n; i++) cout << " " << a[i];
    cout << endl;
}

int main() {
    int n; cin >> n;
    G.resize(n + 1);
    vector<ll> s(n + 1), c(n + 1);
    for (int i = 1; i <= n; i++) cin >> s[i];
    for (int i = 1; i <= n; i++) cin >> c[i];
    for (int i = 0; i < n - 1; i++) {
        int u, v; cin >> u >> v;
        G[u].push_back(v); G[v].push_back(u);
    }

    dfs1(1); dfs2(1, 1);

    ss.resize(n + 1, 0); cc.resize(n + 1, 0); // ss : 元の宿泊費を行きがけ順に並べたもの、cc : インフレ定数の累積和の行きがけ順
    for (int i = 1; i <= n; i++) {
        ss[i] = s[tour[i]]; cc[i] = (c[tour[i]] + cc[i - 1]) % mod;
    }
    //for (int i = 1; i <= n; i++) cout << idx[i] << " "; cout << endl;
    //print(ss); print(cc); print(tour);
    LazySegmentTree seg(ss);

    int q; cin >> q;
    while (q--) {
        int t, x, y; cin >> t >> x >> y;

        // 宿泊費の値上げ
        if (t == 0) {
            ll z; cin >> z;
            
            while (fir[x] != fir[y]) {
                if (idx[fir[x]] > idx[fir[y]]) swap(x, y);
                seg.add(idx[fir[y]], idx[y] + 1, 1, seg.siz + 1, 1, z % mod);
                y = par[fir[y]];
            }
            if (idx[x] > idx[y]) swap(x, y);
            seg.add(idx[x], idx[y] + 1, 1, seg.siz + 1, 1, z % mod);
            //cout << "add " << idx[x] << " " << idx[y] << " " << z << endl;
        }

        // 旅費の算出
        if (t == 1) {
            ll res = 0;
            while (fir[x] != fir[y]) {
                if (idx[fir[x]] > idx[fir[y]]) swap(x, y);
                res += seg.Query(idx[fir[y]], idx[y] + 1, 1, seg.siz + 1, 1); res %= mod;
                y = par[fir[y]];
            }
            if (idx[x] > idx[y]) swap(x, y);
            res += seg.Query(idx[x], idx[y] + 1, 1, seg.siz + 1, 1);
            res %= mod; if (res < 0) res += mod;
            cout << res << endl;
        }
    }
}
0