#define _USE_MATH_DEFINES #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; const int MOD = 1000000007; class DelayExec { public: using T1 = pair; using T2 = long long; // データの初期値、以下の条件を満たすこと // uniteData(v, INIT_DATA) == v static const T1 INIT_DATA; // 遅延の初期値、以下の条件を満たすこと // updateData(prev, size, INIT_DELAY) == prev // updateDelay(x, INIT_DELAY) == x static const T2 INIT_DELAY; // 2つの区間の計算結果v1,v2に対して、 // その2つの区間を統合した区間における計算結果を返す static T1 uniteData(T1 v1, T1 v2){ v1.first += v2.first; v1.first %= MOD; v1.second += v2.second; v2.second %= MOD; return v1; } // 長さがlenの区間における前回の計算結果prevに対して、 // 区間の各要素にパラメータxを用いた更新処理を適用した後の計算結果を返す static T1 updateData(T1 prev, int len, T2 x){ prev.first += prev.second * x; prev.first %= MOD; return prev; } // パラメータx1,x2による2つの更新処理を順に適用した場合に対して、 // 同じ結果になるような1つの更新処理のパラメータを返す static T2 updateDelay(T2 x1, T2 x2){ return (x1 + x2) % MOD; } }; const DelayExec::T1 DelayExec::INIT_DATA = make_pair(0, 0); const DelayExec::T2 DelayExec::INIT_DELAY = 0; template class SegmentTree { private: using T1 = typename D::T1; using T2 = typename D::T2; int n; vector data; vector delay; void updateTree(int a, int b, int k, int l, int r, T2 x){ if(a <= l && r <= b){ data[k] = D::updateData(data[k], r - l, x); delay[k] = D::updateDelay(delay[k], x); } else if(a < r && l < b){ int len = (r - l) / 2; for(int i=0; i<2; ++i){ data[k*2+1+i] = D::updateData(data[k*2+1+i], len, delay[k]); delay[k*2+1+i] = D::updateDelay(delay[k*2+1+i], delay[k]); } delay[k] = D::INIT_DELAY; updateTree(a, b, k*2+1, l, (l+r+1)/2, x); updateTree(a, b, k*2+2, (l+r+1)/2, r, x); data[k] = D::uniteData(data[k*2+1], data[k*2+2]); } } T1 getValue(int a, int b, int k, int l, int r){ if(a <= l && r <= b){ return data[k]; } else if(a < r && l < b){ int len = (r - l) / 2; for(int i=0; i<2; ++i){ data[k*2+1+i] = D::updateData(data[k*2+1+i], len, delay[k]); delay[k*2+1+i] = D::updateDelay(delay[k*2+1+i], delay[k]); } delay[k] = D::INIT_DELAY; T1 v1 = getValue(a, b, k*2+1, l, (l+r+1)/2); T1 v2 = getValue(a, b, k*2+2, (l+r+1)/2, r); return D::uniteData(v1, v2); } else{ return D::INIT_DATA; } } public: SegmentTree(int n0){ n = 1; while(n < n0) n *= 2; data.assign(2*n-1, D::INIT_DATA); delay.assign(2*n-1, D::INIT_DELAY); } SegmentTree(const vector& v) : SegmentTree((int)v.size()){ for(unsigned i=0; i=0; --k) data[k] = D::uniteData(data[k*2+1], data[k*2+2]); } // 区間[a,b)の要素にパラメータxによる更新処理を適用 void update(int a, int b, T2 x){ updateTree(a, b, 0, 0, n, x); } // 区間[a,b)の計算結果を返す T1 get(int a, int b){ return getValue(a, b, 0, 0, n); } // a番目の要素をxで上書きする void set(int a, T1 x){ getValue(a, a+1, 0, 0, n); data[n-1+a] = x; updateTree(a, a+1, 0, 0, n, D::INIT_DELAY); } }; template class HeavyLightDecomposition { private: using T1 = typename D::T1; using T2 = typename D::T2; vector size, depth, parent, top, index; SegmentTree data; // 2回の深さ優先探索によりHL分解を行う void dfs1(const vector >& edges, int curr, int prev) { size[curr] = 1; for(int next : edges[curr]){ if(next == prev) continue; dfs1(edges, next, curr); size[curr] += size[next]; } } void dfs2(const vector >& edges, int curr, int prev, int top2, int& cnt) { index[curr] = cnt; ++ cnt; top[index[curr]] = index[top2]; if(prev != -1){ depth[index[curr]] = depth[index[prev]] + 1; parent[index[curr]] = index[prev]; } int maxSize = 0; int next = -1; for(int to : edges[curr]){ if(to != prev && maxSize < size[to]){ maxSize = size[to]; next = to; } } if(next != -1) dfs2(edges, next, curr, top2, cnt); for(int to : edges[curr]){ if(to != prev && to != next) dfs2(edges, to, curr, to, cnt); } } public: // コンストラクタ HeavyLightDecomposition(const vector >& edges, int root) : data(0) { int n = edges.size(); int cnt = 0; size.resize(n); top.resize(n); index.resize(n); depth.assign(n, 0); parent.assign(n, -1); dfs1(edges, root, -1); dfs2(edges, root, -1, root, cnt); vector size2(n); for(int i=0; i(n); } // コンストラクタ(初期値あり) HeavyLightDecomposition(const vector >& edges, int root, const vector& init) : HeavyLightDecomposition(edges, root) { int n = edges.size(); vector v(n); for(int i=0; i(v); } // a,b間のパスに対してパラメータxによる更新を適用 void updatePath(int a, int b, T2 x){ a = index[a]; b = index[b]; while(top[a] != top[b]){ int a2 = top[a]; int b2 = top[b]; if(depth[a2] < depth[b2]){ swap(a, b); swap(a2, b2); } data.update(a2, a+1, x); a = parent[a2]; } if(depth[a] > depth[b]) swap(a, b); data.update(a, b+1, x); } // a,b間のパスの結果を取得 T1 getPath(int a, int b){ a = index[a]; b = index[b]; T1 ans = D::INIT_DATA; while(top[a] != top[b]){ int a2 = top[a]; int b2 = top[b]; if(depth[a2] < depth[b2]){ swap(a, b); swap(a2, b2); } ans = D::uniteData(ans, data.get(a2, a+1)); a = parent[a2]; } if(depth[a] > depth[b]) swap(a, b); ans = D::uniteData(ans, data.get(a, b+1)); return ans; } // aを根とする部分木に対してパラメータxによる更新を適用 void updateSubTree(int a, T2 x){ a = index[a]; data.update(a, a+size[a], x); } // aを根とする部分木の結果を取得 T1 getSubTree(int a){ a = index[a]; return data.get(a, a+size[a]); } // 部分木のサイズを取得 int getSize(int a){ a = index[a]; return size[a]; } }; int main() { int n; cin >> n; vector > v(n); for(int i=0; i> v[i].first; for(int i=0; i> v[i].second; vector > edges(n); for(int i=0; i> a >> b; -- a; -- b; edges[a].push_back(b); edges[b].push_back(a); } int q; cin >> q; HeavyLightDecomposition<> hld(edges, 0, v); while(--q >= 0){ int t, x, y; cin >> t >> x >> y; -- x; -- y; if(t == 0){ long long z; cin >> z; hld.updatePath(x, y, z); } else{ cout << hld.getPath(x, y).first << endl; } } return 0; }