結果
問題 | No.235 めぐるはめぐる (5) |
ユーザー |
![]() |
提出日時 | 2017-11-05 22:57:42 |
言語 | C++11 (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 1,026 ms / 10,000 ms |
コード長 | 6,551 bytes |
コンパイル時間 | 2,262 ms |
コンパイル使用メモリ | 184,084 KB |
実行使用メモリ | 50,788 KB |
最終ジャッジ日時 | 2024-11-24 02:57:54 |
合計ジャッジ時間 | 8,031 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 3 |
ソースコード
#include <bits/stdc++.h>using namespace std;using VI = vector<int>;using VVI = vector<VI>;using PII = pair<int, int>;using LL = long long;using VL = vector<LL>;using VVL = vector<VL>;using PLL = pair<LL, LL>;using VS = vector<string>;#define ALL(a) begin((a)),end((a))#define RALL(a) (a).rbegin(), (a).rend()#define PB push_back#define EB emplace_back#define MP make_pair#define SZ(a) int((a).size())#define SORT(c) sort(ALL((c)))#define RSORT(c) sort(RALL((c)))#define UNIQ(c) (c).erase(unique(ALL((c))), end((c)))#define FOR(i,a,b) for(int i=(a);i<(b);++i)#define REP(i,n) FOR(i,0,n)#define FF first#define SS secondtemplate<class S, class T>istream& operator>>(istream& is, pair<S,T>& p){return is >> p.FF >> p.SS;}template<class S, class T>ostream& operator<<(ostream& os, const pair<S,T>& p){return os << p.FF << " " << p.SS;}template<class T>void maxi(T& x, T y){if(x < y) x = y;}template<class T>void mini(T& x, T y){if(x > y) x = y;}const double EPS = 1e-10;const double PI = acos(-1.0);const LL MOD = 1000000007;struct Edge{int to, cost;Edge(int t, int c = 0): to(t), cost(c){}bool operator>(const Edge& rhs) const{return cost > rhs.cost;}bool operator<(const Edge& rhs) const{return cost < rhs.cost;}};using Graph = vector<vector<Edge>>;void add_edge(Graph& graph, int u, int v, int cost = 0){graph[u].push_back(Edge(v,cost));graph[v].push_back(Edge(u,cost));}class LazySegT{private:int NN;struct Node{LL dat;LL lazy;LL S;};vector<Node> segT;public:LazySegT(int n, VL& x0, VL& s0){NN = 1;while(NN < n) NN <<= 1;segT.resize(NN*2);for(int i=0;i<n;++i){segT[NN-1+i].dat = x0[i];segT[NN-1+i].S = s0[i];segT[NN-1+i].lazy = 0;}for(int i=NN-2;i>=0;--i){segT[i].dat = (segT[i*2+1].dat + segT[i*2+2].dat) % MOD;segT[i].S = (segT[i*2+1].S + segT[i*2+2].S) % MOD;segT[i].lazy = 0;}}void eval(int k, int l, int r){if(segT[k].lazy == 0) return;(segT[k].dat += segT[k].lazy * segT[k].S % MOD) %= MOD;if(k < NN-1){ // not leaf(segT[2*k+1].lazy += segT[k].lazy) %= MOD;(segT[2*k+2].lazy += segT[k].lazy) %= MOD;}segT[k].lazy = 0;}void update(int a, int b, LL c, int k, int l, int r){eval(k,l,r);if(r <= a || b <= l) return;if(a <= l && r <= b){(segT[k].lazy += c) %= MOD;eval(k,l,r);}else{update(a, b, c, k*2+1, l, (l+r)/2);update(a, b, c, k*2+2, (l+r)/2, r);segT[k].dat = (segT[k*2+1].dat + segT[k*2+2].dat) % MOD;}}// dat[idx] += c, a <= idx < bvoid update(int a, int b, LL c){update(a, b, c, 0, 0, NN);}LL query(int a, int b, int k, int l, int r){eval(k,l,r);if(r <= a || b <= l) return 0;if(a <= l && r <= b) return segT[k].dat;else{LL vl = query(a, b, k*2+1, l, (l+r)/2);LL vr = query(a, b, k*2+2, (l+r)/2, r);segT[k].dat = (segT[k*2+1].dat + segT[k*2+2].dat) % MOD;return (vl+vr) % MOD;}}LL query(int a, int b){return query(a, b, 0, 0, NN);}};/*** HL分解** あらゆる部分木の深さがO(log n)になるように分解する。* 部分木のうちサイズが最も大きいものへの辺をHeavy、それ以外をLightに分ける。* Heavyな辺はたかだか一つであるのでSegment Treeなどで管理可能。*/struct HL{int N;VI depth;VI par;VI sz;//! 辺のコストは頂点に移すVI xs;//! 頂点が所属するHeavyのidVI heavy_id;//! 何番目の頂点かVI heavy_nth;//! heavys[id] := {idのHeavyの頂点の列}VVI heavys;//! Heavyからなる部分木としたときの親のheavy_idVI heavy_par;//! heavyの数int H;HL(const Graph& G, int root = 0, const VI& xs_ = {}){N = SZ(G);depth.assign(N, 0);par.assign(N, -1);sz.assign(N, 1);if(!xs_.empty())xs = xs_;elsexs.assign(N, 0);heavy_id.assign(N, -1);heavy_nth.assign(N, 0);heavys.assign(N, {});heavy_par.assign(N, -1);function<void(int,int)> init = [&](int u, int p){par[u] = p;for(auto& e: G[u]){if(e.to == p) continue;depth[e.to] = depth[u] + 1;init(e.to, u);sz[u] += sz[e.to];if(xs_.empty())xs[e.to] = e.cost;}};depth[root] = 0;init(root, -1);H = 1;function<void(int,int)> calcHL = [&](int u, int p){heavy_nth[u] = SZ(heavys[heavy_id[u]]);heavys[heavy_id[u]].PB(u);int max_u = -1;for(auto& e: G[u]){if(e.to == p) continue;if(max_u < 0 || sz[max_u] < sz[e.to])max_u = e.to;}if(max_u < 0) return;heavy_id[max_u] = heavy_id[u];calcHL(max_u, u);for(auto& e: G[u]){if(e.to == p || e.to == max_u) continue;heavy_id[e.to] = H++;calcHL(e.to, u);heavy_par[heavy_id[e.to]] = heavy_id[u];}};heavy_id[root] = 0;calcHL(root, -1);}int LCA(int u, int v){while(true){if(heavy_id[u] == heavy_id[v])return (depth[u] <= depth[v]? u: v);int ru = heavys[heavy_id[u]][0];int rv = heavys[heavy_id[v]][0];if(depth[ru] < depth[rv])v = par[rv];elseu = par[ru];}}vector<LazySegT> segs;void initSegs(VI& cs){REP(i,H){int n = SZ(heavys[i]);VL x0(n), s0(n);REP(k,n){int id = heavys[i][k];x0[k] = xs[id];s0[k] = cs[id];}segs.EB(n, x0, s0);}}// Require: p is ancestor of uvoid add(int p, int u, LL x){while(heavy_id[p] != heavy_id[u]){int hid = heavy_id[u];segs[hid].update(0, heavy_nth[u]+1, x);u = par[heavys[hid][0]];}int hid = heavy_id[u];segs[hid].update(heavy_nth[p], heavy_nth[u]+1, x);}// Require: p is ancestor of uLL query(int p, int u){LL res = 0;while(heavy_id[p] != heavy_id[u]){int hid = heavy_id[u];(res += segs[hid].query(0, heavy_nth[u]+1)) %= MOD;u = par[heavys[hid][0]];}int hid = heavy_id[u];(res += segs[hid].query(heavy_nth[p], heavy_nth[u]+1)) %= MOD;return res;}};int main(){cin.tie(0);ios_base::sync_with_stdio(false);int N;cin >> N;VI xs(N), cs(N);REP(i,N) cin >> xs[i];REP(i,N) cin >> cs[i];Graph G(N);REP(i,N-1){int a, b;cin >> a >> b;--a;--b;add_edge(G, a, b);}auto hl = HL(G, 0, xs);hl.initSegs(cs);int Q;cin >> Q;while(Q--){int T;int x, y, z;cin >> T >> x >> y;--x;--y;if(!T){cin >> z;int lca = hl.LCA(x, y);hl.add(lca, x, z);hl.add(lca, y, z);hl.add(lca, lca, MOD-z);}else{int lca = hl.LCA(x, y);cout << (hl.query(lca, x) + hl.query(lca, y) + MOD - hl.query(lca, lca))%MOD << endl;}}return 0;}