結果
問題 | No.235 めぐるはめぐる (5) |
ユーザー | yuji9511 |
提出日時 | 2020-05-04 18:50:36 |
言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 6,695 bytes |
コンパイル時間 | 2,653 ms |
コンパイル使用メモリ | 188,228 KB |
実行使用メモリ | 54,720 KB |
最終ジャッジ日時 | 2024-06-24 20:20:32 |
合計ジャッジ時間 | 7,001 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | WA | - |
testcase_01 | AC | 693 ms
54,720 KB |
testcase_02 | AC | 999 ms
54,132 KB |
ソースコード
/*** author: yuji9511 ***/ #include <bits/stdc++.h> using namespace std; using ll = long long; using lpair = pair<ll, ll>; const ll MOD = 1e9+7; const ll INF = 1e18; #define rep(i,m,n) for(ll i=(m);i<(n);i++) #define rrep(i,m,n) for(ll i=(m);i>=(n);i--) #define printa(x,n) for(ll i=0;i<n;i++){cout<<(x[i])<<" \n"[i==n-1];}; void print() {} template <class H,class... T> void print(H&& h, T&&... t){cout<<h<<" \n"[sizeof...(t)==0];print(forward<T>(t)...);} class HeavyLightDecomposition { private: void dfs_sz(ll v) { for(ll &u : G[v]) if(u == par[v]) swap(u,G[v].back()); if(~par[v]) G[v].pop_back(); for(ll &u : G[v]){ par[u] = v; dep[u] = dep[v] + 1; dfs_sz(u); sub[v] += sub[u]; if(sub[u] > sub[G[v][0]]) swap(u,G[v][0]); } } void dfs_hld(ll v,ll c,ll &pos) { vid[v] = pos++; inv[vid[v]] = v; type[v] = c; for(ll u : G[v]){ if(u == par[v]) continue; head[u] = (u == G[v][0] ? head[v] : u); dfs_hld(u,c,pos); } } public: vector< vector<ll> > G; vector<ll> vid, head, sub, par, dep, inv, type; ll N; HeavyLightDecomposition(ll n): G(n), vid(n,-1), head(n), sub(n,1), par(n,-1), dep(n,0), inv(n), type(n){ N = n; } void add_edge(ll u, ll v) { G[u].emplace_back(v); G[v].emplace_back(u); } void build(vector<ll> rs = {0}) { ll c = 0, pos = 0; for(ll r : rs){ dfs_sz(r); head[r] = r; dfs_hld(r, c++, pos); } } ll lca(ll u,ll v){ while(1){ if(vid[u] > vid[v]) swap(u,v); if(head[u] == head[v]) return u; v = par[head[v]]; } } ll distance(ll u,ll v){ return dep[u] + dep[v] - 2 * dep[lca(u,v)]; } // for_each(vertex) // [l, r) <- attention!! template<typename F> void for_each(ll u, ll v, const F& f) { while(1){ if(vid[u] > vid[v]) swap(u,v); f(max(vid[head[v]], vid[u]), vid[v]+1); if(head[u] != head[v]) v=par[head[v]]; else break; } } vector<lpair> query(ll u, ll v){ vector<lpair> res; while(1){ if(vid[u] > vid[v]) swap(u,v); res.push_back({max(vid[head[v]], vid[u]), vid[v]+1}); if(head[u] != head[v]) v = par[head[v]]; else break; } return res; } template<typename T,typename Q,typename F> T for_each(ll u, ll v, T ti,const Q &q,const F &f){ T l = ti,r = ti; while(1){ if(vid[u] > vid[v]){ swap(u, v); swap(l, r); } l=f(l, q(max(vid[head[v]],vid[u]), vid[v]+1)); if(head[u] != head[v]) v = par[head[v]]; else break; } return f(l, r); } // for_each(edge) // [l, r) <- attention!! template<typename F> void for_each_edge(ll u, ll v,const F& f) { while(1){ if(vid[u] > vid[v]) swap(u,v); if(head[u] != head[v]){ f(vid[head[v]], vid[v]+1); v = par[head[v]]; }else{ if(u != v) f(vid[u]+1, vid[v]+1); break; } } } vector<lpair> query_edge(ll u, ll v){ vector<lpair> res; while(1){ if(vid[u] > vid[v]) swap(u,v); if(head[u] != head[v]){ res.push_back({vid[head[v]], vid[v]+1}); v = par[head[v]]; }else{ if(u != v) res.push_back({vid[u]+1, vid[v]+1}); break; } } return res; } }; struct AddLazySegmentTree { private: ll n; vector<ll> node, lazy, cost; public: AddLazySegmentTree(vector<ll> v, vector<ll> c) { ll sz = (ll)v.size(); n = 1; while(n < sz) n *= 2; node.resize(2*n-1); lazy.resize(2*n-1, 0); cost.resize(2*n-1, 0); for(ll i=0; i<sz; i++) node[i+n-1] = v[i]; for(ll i=n-2; i>=0; i--) node[i] = node[i*2+1] + node[i*2+2]; for(ll i=0; i<sz; i++) cost[i+n-1] = c[i]; for(ll i=n-2; i>=0; i--) cost[i] = cost[i*2+1] + cost[i*2+2]; } void eval(ll k, ll l, ll r) { if(lazy[k] != 0) { node[k] += lazy[k] * cost[k] % MOD; node[k] %= MOD; if(r - l > 1) { lazy[2*k+1] += lazy[k]; lazy[2*k+2] += lazy[k]; lazy[2*k+1] %= MOD; lazy[2*k+2] %= MOD; } lazy[k] = 0; } } void add(ll a, ll b, ll x, ll k=0, ll l=0, ll r=-1) { if(r < 0) r = n; eval(k, l, r); if(b <= l || r <= a) return; if(a <= l && r <= b) { lazy[k] += x; lazy[k] %= MOD; eval(k, l, r); } else { add(a, b, x, 2*k+1, l, (l+r)/2); add(a, b, x, 2*k+2, (l+r)/2, r); node[k] = node[2*k+1] + node[2*k+2]; node[k] %= MOD; } } ll getsum(ll a, ll b, ll k=0, ll l=0, ll r=-1) { if(r < 0) r = n; eval(k, l, r); if(b <= l || r <= a) return 0; if(a <= l && r <= b) return node[k]; ll vl = getsum(a, b, 2*k+1, l, (l+r)/2); ll vr = getsum(a, b, 2*k+2, (l+r)/2, r); return vl + vr; } }; ll S[200010], C[200010]; vector<ll> tree[200010]; int main(){ cin.tie(0); ios::sync_with_stdio(false); ll N; cin >> N; HeavyLightDecomposition hld(N); rep(i,0,N) cin >> S[i]; rep(i,0,N) cin >> C[i]; rep(i,0,N-1){ ll a,b; cin >> a >> b; a--; b--; hld.add_edge(a,b); } hld.build(); // printa(hld.inv, N); auto pos = hld.inv; vector<ll> v(N,0), c(N,0); rep(i,0,N){ v[i] = S[pos[i]]; c[i] = C[pos[i]]; } // printa(c, N); AddLazySegmentTree sg(v,c); ll Q; cin >> Q; while(Q--){ ll t; cin >> t; if(t == 1){ ll x,y; cin >> x >> y; x--; y--; ll ans = 0; auto p = hld.query(x,y); for(auto &e: p){ ans += sg.getsum(e.first, e.second); ans %= MOD; } print(ans); }else{ ll x,y,z; cin >> x >> y >> z; x--; y--; auto p = hld.query(x,y); for(auto &e: p){ sg.add(e.first, e.second,z); } } } }