結果
| 問題 |
No.235 めぐるはめぐる (5)
|
| コンテスト | |
| ユーザー |
 pekempey
|
| 提出日時 | 2015-09-06 21:13:49 |
| 言語 | C++11（廃止可能性あり） (gcc 13.3.0) |
| 結果 |
AC
|
| 実行時間 | 1,032 ms / 10,000 ms |
| コード長 | 4,998 bytes |
| コンパイル時間 | 1,659 ms |
| コンパイル使用メモリ | 178,768 KB |
| 実行使用メモリ | 73,148 KB |
| 最終ジャッジ日時 | 2024-07-19 04:42:36 |
| 合計ジャッジ時間 | 6,206 ms |
|
ジャッジサーバーID （参考情報） |
judge2 / judge4 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 3 |
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:199:25: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
199 | rep (i, N) scanf("%d", &S[i]);
| ~~~~~^~~~~~~~~~~~~
main.cpp:200:25: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
200 | rep (i, N) scanf("%d", &C[i]);
| ~~~~~^~~~~~~~~~~~~
main.cpp:217:22: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
217 | scanf("%d", &q);
| ~~~~~^~~~~~~~~~
main.cpp:220:30: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
220 | scanf("%d%d%d", &x, &y, &z);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~
main.cpp:225:30: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
225 | scanf("%d%d", &x, &y);
| ~~~~~^~~~~~~~~~~~~~~~
ソースコード
#include <bits/stdc++.h>
#define rep(i, a) for (int i = 0; i < (a); i++)
#define rep2(i, a, b) for (int i = (a); i < (b); i++)
#define repr(i, a) for (int i = (a) - 1; i >= 0; i--)
#define repr2(i, a, b) for (int i = (b) - 1; i >= (a); i--)
using namespace std;
typedef long long ll;
const int inf = 1e9;
const ll mod = 1e9 + 7;
struct HL {
vector<vector<int>> G, path;
vector<int> parent, head, order, heads, heavy, depth;
int root;
HL(int n) : G(n), heavy(n, -1), parent(n), head(n), order(n), path(n), depth(n) {}
void add(int u, int v) {
G[u].push_back(v);
G[v].push_back(u);
}
int dfs(int curr, int prev = -1) {
int res = 1;
head[curr] = curr;
parent[curr] = prev;
int maxv = -1;
for (int next : G[curr]) if (next != prev) {
int d = dfs(next, curr);
res += d;
if (maxv < d) maxv = d, heavy[curr] = next;
}
return res;
}
void dfs2(int curr, int prev = -1) {
if (head[curr] == curr) heads.push_back(curr);
path[head[curr]].push_back(curr);
for (int next : G[curr]) if (next != prev) {
if (next == heavy[curr]) {
head[next] = head[curr];
order[next] = order[curr] + 1;
}
depth[next] = depth[curr] + (next != heavy[curr]);
dfs2(next, curr);
}
}
void build(int root = 0) {
this->root = root;
dfs(root);
dfs2(root);
}
struct Iterator {
int u, v;
HL *hl;
Iterator(HL *hl, int u, int v) : hl(hl), u(u), v(v) {}
// head, [from, to)
tuple<int, int, int> next() {
if (hl->depth[u] == hl->depth[v]) {
if (hl->head[u] == hl->head[v]) {
auto m = minmax(hl->order[u], hl->order[v]);
u = -1;
return make_tuple(hl->head[v], m.first, m.second + 1);
}
}
if (hl->depth[u] < hl->depth[v]) swap(u, v);
int pu = u;
u = hl->parent[hl->head[u]];
return make_tuple(hl->head[pu], 0, hl->order[pu] + 1);
}
bool has_next() {
return u != -1;
}
};
Iterator iterator(int u, int v) {
return Iterator(this, u, v);
}
};
ll modulo(ll a) {
a %= mod; a += mod; a %= mod;
return a;
}
struct SegmentTree {
vector<ll> seg, lazy, weight, wsum;
int size;
void init(int n) {
size = 1;
while (size < n) size *= 2;
seg.resize(size * 2);
lazy.resize(size * 2);
weight.resize(size);
}
void set_value(int k, ll v) {
seg[k + size - 1] = v;
}
void set_weight(int k, ll w) {
weight[k] = w;
}
void build() {
wsum.resize(size + 1);
rep (i, size) {
wsum[i + 1] += wsum[i] + weight[i];
wsum[i + 1] %= mod;
}
repr (i, size - 1) {
seg[i] = seg[i * 2 + 1] + seg[i * 2 + 2];
seg[i] %= mod;
}
}
void evallazy(int k, int l, int r) {
seg[k] += lazy[k] * (wsum[r] - wsum[l]);
seg[k] = modulo(seg[k]);
if (r - l > 1) {
(lazy[k * 2 + 1] += lazy[k]) %= mod;
(lazy[k * 2 + 2] += lazy[k]) %= mod;
}
lazy[k] = 0;
}
void update(int a, int b, ll v, int k, int l, int r) {
evallazy(k, l, r);
if (r <= a || b <= l) return;
if (a <= l && r <= b) {
lazy[k] = v;
evallazy(k, l, r);
} else {
update(a, b, v, k * 2 + 1, l, (l + r) / 2);
update(a, b, v, k * 2 + 2, (l + r) / 2, r);
seg[k] = seg[k * 2 + 1] + seg[k * 2 + 2];
seg[k] %= mod;
}
}
void update(int a, int b, ll v) {
update(a, b, v, 0, 0, size);
}
ll query(int a, int b, int k, int l, int r) {
evallazy(k, l, r);
if (r <= a || b <= l) return 0;
if (a <= l && r <= b) return seg[k];
ll res = 0;
res += query(a, b, k * 2 + 1, l, (l + r) / 2);
res += query(a, b, k * 2 + 2, (l + r) / 2, r);
return res % mod;
}
ll query(int a, int b) {
return query(a, b, 0, 0, size);
}
};
struct HLSolver {
HL hl;
vector<SegmentTree> tr;
HLSolver(int n) : hl(n), tr(n) {}
void add(int u, int v) {
hl.add(u, v);
}
void build() {
hl.build();
for (int h : hl.heads) {
tr[h].init(hl.path[h].size());
}
}
void set(int u, int x, int y) {
tr[hl.head[u]].set_value(hl.order[u], x);
tr[hl.head[u]].set_weight(hl.order[u], y);
}
void build_segment_tree() {
for (int h : hl.heads) {
tr[h].build();
}
}
void update(int u, int v, ll x) {
auto it = hl.iterator(u, v);
while (it.has_next()) {
auto t = it.next();
int h = get<0>(t);
int l = get<1>(t);
int r = get<2>(t);
tr[h].update(l, r, x);
}
}
ll query(int u, int v) {
ll res = 0;
auto it = hl.iterator(u, v);
while (it.has_next()) {
auto t = it.next();
int h = get<0>(t);
int l = get<1>(t);
int r = get<2>(t);
res += tr[h].query(l, r);
res %= mod;
}
return res;
}
};
int main() {
int N;
cin >> N;
vector<int> S(N), C(N);
rep (i, N) scanf("%d", &S[i]);
rep (i, N) scanf("%d", &C[i]);
HLSolver hl(N);
rep (i, N - 1) {
int a, b;
cin >> a >> b;
a--; b--;
hl.add(a, b);
}
hl.build();
rep (i, N) {
hl.set(i, S[i], C[i]);
}
hl.build_segment_tree();
int Q;
cin >> Q;
while (Q--) {
int q;
scanf("%d", &q);
if (q == 0) {
int x, y, z;
scanf("%d%d%d", &x, &y, &z);
x--; y--;
hl.update(x, y, z);
} else {
int x, y;
scanf("%d%d", &x, &y);
x--; y--;
printf("%d\n", (int)hl.query(x, y));
}
}
}