結果
| 問題 | No.235 めぐるはめぐる (5) |
| ユーザー |
 hiikunZ
|
| 提出日時 | 2024-03-20 21:55:04 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 6,406 ms / 10,000 ms |
| コード長 | 6,008 bytes |
| コンパイル時間 | 2,901 ms |
| コンパイル使用メモリ | 226,668 KB |
| 最終ジャッジ日時 | 2025-02-20 09:04:03 |
|
ジャッジサーバーID （参考情報） |
judge2 / judge1 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 3 |
ソースコード
// #pragma GCC target("avx2")#pragma GCC optimize("Ofast,unroll-loops")#include<bits/stdc++.h>using namespace std;using ll = long long int;const ll MOD = 1000000007;ll N;vector<ll> S(200000),C(200000),seen(200000,0),siz(200000,0),par(200000,-1),root(200000,-1),id(200000,-1),dep(200000,0);vector<vector<ll>> GG(200000),G(200000);void dfs1(ll x){seen[x] = 1;siz[x] = 1;for(ll i = 0;i < (ll)GG[x].size();i++){ll y = GG[x][i];if(seen[y] == 1) continue;dep[y] = dep[x] + 1;G[x].emplace_back(y);dfs1(y);siz[x] += siz[y];}}ll I = 0;void dfs2(ll x){id[x] = I;I++;for(ll i = 1;i < (ll)G[x].size();i++){if(siz[G[x][i]] > siz[G[x][0]]){swap(G[x][i],G[x][0]);}}for(ll i = 0;i < (ll)G[x].size();i++){ll y = G[x][i];if(i == 0) root[y] = root[x];else root[y] = y;par[y] = x;dfs2(y);}}vector<ll> O(300000,0),O_R(300000,0),A(800000,0),E(800000,0),R_L(800000),R_R(800000); // A は合計void eval(ll x){ll s = (O_R[R_R[x]] - O_R[R_L[x]]) % MOD;A[x] += (s * E[x]) % MOD;A[x] %= MOD;if(x < N){E[x * 2] += E[x];E[x * 2] %= MOD;E[x * 2 + 1] += E[x];E[x * 2 + 1] %= MOD;}E[x] = 0;}void ue_update(ll x){ll X = 0;while((x >> X) > 0) X++;while(X > 0){X--;eval(x >> X);}}void reeval(ll x){while(x > 0){eval(x);if(x < N){eval(x * 2);eval(x * 2 + 1);A[x] = (A[x * 2] + A[x * 2 + 1]) % MOD;}x /= 2;}}void add(ll l,ll r,ll x){if(l >= r) return;x %= MOD;if(x < 0) x += MOD;//cerr << "add("<<l<<","<<r<<","<<x<<")"<<endl;l += N;r += N;ll Llog = l,Rlog = r;ue_update(l);ue_update(r - 1);while(l < r){if(l & 1){eval(l);E[l] += x;E[l] %= MOD;eval(l);l++;}if(r & 1){r--;eval(r);E[r] += x;E[r] %= MOD;eval(r);}l /= 2;r /= 2;}reeval(Llog);reeval(Rlog- 1);}ll query(ll l,ll r){if(l >= r) return 0;//cerr<<"query("<<l<<","<<r<<")";l += N;r += N;ll ans = 0;ue_update(l);ue_update(r - 1);while(l < r){if(l & 1){eval(l);ans += A[l];ans %= MOD;l++;}if(r & 1){r--;eval(r);ans += A[r];ans %= MOD;}l /= 2;r /= 2;}//cerr << " = " << ans << endl;return ans;}vector<vector<ll>> D(30,vector<ll>(200000,0));ll lca(ll x,ll y){if(dep[x] < dep[y]) swap(x,y);for(ll i = 28;i >= 0;i--){ll xx = D[i][x];if(dep[xx] >= dep[y]) x = xx;}if(x == y) return x;for(ll i = 28;i >= 0;i--){ll xx = D[i][x],yy = D[i][y];if(xx != yy){x = xx;y = yy;}}return D[0][x];}int main(){cin >> N;for(ll i = 0;i < N;i++) cin >> S[i];for(ll j = 0;j < N;j++) cin >> C[j];for(ll i = 0;i < N - 1;i++){ll a,b;cin >> a >> b;a--;b--;GG[a].emplace_back(b);GG[b].emplace_back(a);}dfs1(0);root[0] = 0;dfs2(0);for(ll i = 1;i < N;i++){D[0][i] = par[i];}for(ll i = 0;i < 29;i++){for(ll j = 0;j < N;j++){D[i + 1][j] = D[i][D[i][j]];}}for(ll i = 0;i < N;i++){//cerr<<id[i]<<endl;O[id[i]] = C[i];A[N + id[i]] = S[i];R_L[N + i] = i;R_R[N + i] = i + 1;}for(ll i = 0;i < N;i++){O_R[i + 1] = O_R[i] + O[i];O_R[i + 1] %= MOD;}for(ll i = N - 1;i > 0;i--){A[i] = A[i * 2] + A[i * 2 + 1];A[i] %= MOD;R_L[i] = R_L[i * 2];R_R[i] = R_R[i * 2 + 1];}ll Q;cin >> Q;for(ll q = 0;q < Q;q++){ll t;cin >> t;if(t == 0){ll x,y,z;cin >> x >> y >> z;x--;y--;ll a = lca(x,y);while(root[x] != root[a]){ll id_r = id[root[x]],id_x = id[x];add(id_r,id_x + 1,z);x = par[root[x]];}{ll id_a = id[a],id_x = id[x];add(id_a,id_x + 1,z);}while(root[y] != root[a]){ll id_r = id[root[y]],id_y = id[y];add(id_r,id_y + 1,z);y = par[root[y]];}{ll id_a = id[a],id_y = id[y];add(id_a,id_y + 1,z);}ll id_a = id[a];add(id_a,id_a + 1,-z);}else{ll x,y;cin >> x >> y;x--;y--;ll a = lca(x,y);ll ans = 0;while(root[x] != root[a]){ll id_r = id[root[x]],id_x = id[x];ans += query(id_r,id_x + 1);ans %= MOD;x = par[root[x]];}{ll id_a = id[a],id_x = id[x];ans += query(id_a,id_x + 1);ans %= MOD;}while(root[y] != root[a]){ll id_r = id[root[y]],id_y = id[y];ans += query(id_r,id_y + 1);ans %= MOD;y = par[root[y]];}{ll id_a = id[a],id_y = id[y];ans += query(id_a,id_y + 1);ans %= MOD;}ll id_a = id[a];ans -= query(id_a,id_a + 1);ans %= MOD;if(ans < 0) ans += MOD;cout << ans << endl;}}}