結果
問題 | No.235 めぐるはめぐる (5) |
ユーザー | Luzhiled |
提出日時 | 2017-07-07 08:44:26 |
言語 | C++11 (gcc 11.4.0) |
結果 |
RE
|
実行時間 | - |
コード長 | 5,330 bytes |
コンパイル時間 | 1,589 ms |
コンパイル使用メモリ | 175,628 KB |
実行使用メモリ | 25,588 KB |
最終ジャッジ日時 | 2024-10-06 05:50:30 |
合計ジャッジ時間 | 6,195 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | RE | - |
testcase_01 | RE | - |
testcase_02 | RE | - |
ソースコード
#include <bits/stdc++.h> using namespace std; #define fs first #define sc second #define pb emplace_back #define mp make_pair #define all(v) v.begin(), v.end() #define rall(v) v.rbegin(), v.rend() #define rep(i, n) for (int i = 0; i < (int)(n); ++i) using pii = pair<int, int>; using vi = vector<int>; using lint = long long; const int inf = 1001001001; const lint linf = 1001001001001001001ll; const int mod = 1e9 + 7; const int dx[]{0, 1, 0, -1, -1, -1, 1, 1}, dy[]{1, 0, -1, 0, -1, 1, -1, 1}; template<typename T> inline bool chmin(T &a, T b) { if (a > b) { a = b; } return a > b; } template<typename T> inline bool chmax(T &a, T b) { if (a < b) { a = b; } return a < b; } template<typename T> inline void print(const T &x, string s = "\n") { cout << x << s; } template<typename T> inline void print(const vector<T> &v, string s = " ") { if (!v.size()) puts(""); rep(i, v.size()) cout << v[i] << (i + 1 == v.size() ? "\n" : s); } inline bool inside(int y, int x, int H, int W) { return 0 <= y && y < H && 0 <= x && x < W; } inline lint in() { lint x; std::cin>>x; return x; } int n; vi s, c, v; struct HLDecomposition { vector<vector<int>> g; vector<int> vid, head, heavy, parent, depth, inv; HLDecomposition(int n):g(n),vid(n,-1),head(n),heavy(n,-1),parent(n),depth(n),inv(n) {} void add(int u, int v) { g[u].push_back(v); g[v].push_back(u); } void build() { dfs(0, -1); bfs(); } int dfs(int curr, int prev) { parent[curr] = prev; int sub = 1, max_sub = 0; for (int next : g[curr]) if (next != prev) { depth[next] = depth[curr] + 1; int sub_next = dfs(next, curr); sub += sub_next; if (max_sub < sub_next) max_sub = sub_next, heavy[curr] = next; } return sub; } void bfs() { int k = 0; queue<int> q({ 0 }); while (!q.empty()) { int h = q.front(); q.pop(); for (int i = h; i != -1; i = heavy[i]) { vid[i] = k++; inv[vid[i]] = i; head[i] = h; for (int j : g[i]) if (j != parent[i] && j != heavy[i]) q.push(j); } } } void for_each(int u, int v, function<void(int, int)> f) { if (vid[u] > vid[v]) swap(u, v); f(max(vid[head[v]], vid[u]), vid[v]); if (head[u] != head[v]) for_each(u, parent[head[v]], f); } void for_each_directed(int u, int v, function<void(int, int, int)> f) { if (vid[u] > vid[v]) { f(max(vid[head[u]], vid[v]), vid[u], 1); if (head[u] != head[v]) for_each_directed(parent[head[u]], v, f); } else { f(max(vid[head[v]], vid[u]), vid[v], 0); if (head[u] != head[v]) for_each_directed(u, parent[head[v]], f); } } void for_each_edge(int u, int v, function<void(int, int)> f) { if (vid[u] > vid[v]) swap(u, v); if (head[u] != head[v]) { f(vid[head[v]], vid[v]); for_each_edge(u, parent[head[v]], f); } else { if (u != v) f(vid[u] + 1, vid[v]); } } int ancestor(int u, int d) { while (true) { if (depth[head[u]] > depth[u] - d) { d -= depth[u] - depth[head[u]] + 1; if (head[u] == 0) return 0; u = parent[head[u]]; } else { return inv[vid[u] - d]; } } } int lca(int u, int v) { if (vid[u] > vid[v]) swap(u, v); if (head[u] == head[v]) return u; return lca(u, parent[head[v]]); } int distance(int u, int v) { return depth[u] + depth[v] - 2 * depth[lca(u, v)]; } }; const int N = 1 << 17; long long seg_sum[N * 2], seg_add[N * 2]; void init() { int m = n; n = 1; while (n < m) n *= 2; } void update(int a, int b, lint v, int k = 1, int l = 0, int r = N) { if (r <= a || b <= l) return; if (a <= l && r <= b) { seg_add[k] += v; seg_sum[k] += v * (r - l); return; } update(a, b, v, k * 2 + 0, l, (l + r) / 2); update(a, b, v, k * 2 + 1, (l + r) / 2, r); seg_sum[k] = seg_sum[k * 2 + 0] + seg_sum[k * 2 + 1] + seg_add[k] * (r - l); } void add(int a, int b, lint v, int k = 1, int l = 0, int r = N) { if (r <= a || b <= l) return; if (a <= l && r <= b) { seg_add[k] += v; seg_sum[k] += v * (c[r] - c[l]); return; } add(a, b, v, k * 2 + 0, l, (l + r) / 2); add(a, b, v, k * 2 + 1, (l + r) / 2, r); seg_sum[k] = seg_sum[k * 2 + 0] + seg_sum[k * 2 + 1] + seg_add[k] * (c[r] - c[l]); } lint sum(int a, int b, int k = 1, int l = 0, int r = N) { if (r <= a || b <= l) return 0; if (a <= l && r <= b) return seg_sum[k]; lint sl = sum(a, b, k * 2 + 0, l, (l + r) / 2); lint sr = sum(a, b, k * 2 + 1, (l + r) / 2, r); return sl + sr + seg_add[k] * (c[r] - c[l]); } void po() { for (int i = 0; i < n; ++i) { cout << sum(i, i + 1) << " "; } puts(""); } signed main() { cin >> n; HLDecomposition hld(n); rep(i, n) s.pb(in()); rep(i, n) v.pb(in()); rep(i, n - 1) { int a = in() - 1, b = in() - 1; hld.add(a, b); } hld.build(); init(); c.resize(n + 1); rep(i, n) { hld.for_each(i, i, [&](int l, int r){ update(l, r + 1, s[i]); c[l + 1] = v[i]; }); } //print(c); rep(i, n) c[i + 1] += c[i]; int q = in(); rep(_, q) { int f = in(); if (f) { lint ans = 0; int u = in() - 1, v = in() - 1; hld.for_each(u, v, [&](int l, int r) { ans += sum(l, r + 1); ans %= mod; }); print(ans); } else { int u = in() - 1, v = in() - 1, z = in(); hld.for_each(u, v, [&](int l, int r) { add(l, r + 1, z); //printf("(%d, %d] ", l, r); }); //puts(""); } //po(); } }