結果
| 問題 | No.235 めぐるはめぐる (5) |
| ユーザー |
 pekempey
|
| 提出日時 | 2015-11-08 01:14:16 |
| 言語 | C++11 (gcc 11.4.0) |
| 結果 |
AC
|
| 実行時間 | 2,076 ms / 10,000 ms |
| コード長 | 4,965 bytes |
| コンパイル時間 | 1,696 ms |
| コンパイル使用メモリ | 175,384 KB |
| 実行使用メモリ | 32,936 KB |
| 最終ジャッジ日時 | 2024-09-13 14:06:38 |
| 合計ジャッジ時間 | 11,040 ms |
|
ジャッジサーバーID （参考情報） |
judge4 / judge3 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 2,076 ms
32,136 KB |
| testcase_01 | AC | 1,286 ms
32,936 KB |
| testcase_02 | AC | 1,900 ms
32,292 KB |
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:157:21: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
157 | rep (i, N) scanf("%d", &S[i]);
| ~~~~~^~~~~~~~~~~~~
main.cpp:158:21: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
158 | rep (i, N) scanf("%d", &C[i]);
| ~~~~~^~~~~~~~~~~~~
main.cpp:176:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
176 | scanf("%d", &q);
| ~~~~~^~~~~~~~~~
main.cpp:179:18: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
179 | scanf("%d%d%d", &x, &y, &z);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~
main.cpp:188:18: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
188 | scanf("%d%d", &x, &y);
| ~~~~~^~~~~~~~~~~~~~~~
ソースコード
#include <bits/stdc++.h>
#define GET_MACRO(a, b, c, NAME, ...) NAME
#define rep(...) GET_MACRO(__VA_ARGS__, rep3, rep2)(__VA_ARGS__)
#define rep2(i, a) rep3 (i, 0, a)
#define rep3(i, a, b) for (int i = (a); i < (b); i++)
#define repr(...) GET_MACRO(__VA_ARGS__, repr3, repr2)(__VA_ARGS__)
#define repr2(i, a) repr3 (i, 0, a)
#define repr3(i, a, b) for (int i = (b) - 1; i >= (a); i--)
#define chmin(a, b) ((b) < a && (a = (b), true))
#define chmax(a, b) (a < (b) && (a = (b), true))
using namespace std;
typedef long long ll;
const ll mod = 1e9 + 7;
ll modulo(ll a) {
a %= mod; a += mod; a %= mod;
return a;
}
struct HL {
vector<vector<int>> g;
vector<int> heavy, vid, parent, depth, head;
HL(int n) : g(n), heavy(n), vid(n, -1), parent(n), depth(n), head(n) {
for (int i = 0; i < n; i++) head[i] = i;
}
void add(int u, int v) {
g[u].push_back(v);
g[v].push_back(u);
}
void build() {
dfs(0, -1);
int k = 0;
rep (i, g.size()) if (vid[i] == -1) dfs2(i, -1, k);
}
int dfs(int curr, int prev) {
int res = 1;
parent[curr] = prev;
pair<int, int> mx(-1, -1);
for (int next : g[curr]) if (next != prev) {
depth[next] = depth[curr] + 1;
int ret = dfs(next, curr);
res += ret;
mx = max(mx, make_pair(ret, next));
}
heavy[curr] = mx.second;
return res;
}
void dfs2(int curr, int prev, int &k) {
vid[curr] = k++;
if (heavy[curr] != -1) {
int next = heavy[curr];
head[next] = head[curr];
dfs2(next, curr, k);
}
}
struct Iterator {
int u, v;
HL *hl;
Iterator(HL *hl, int u, int v) : hl(hl), u(u), v(v) {}
// [a, b)
pair<int, int> next() {
if (hl->head[u] == hl->head[v]) {
auto m = minmax(hl->vid[u], hl->vid[v]);
u = -1;
return {m.first, m.second + 1};
}
if (hl->depth[hl->head[u]] < hl->depth[hl->head[v]]) swap(u, v);
int pu = u;
u = hl->parent[hl->head[u]];
return {hl->vid[hl->head[pu]], hl->vid[pu] + 1};
}
bool has_next() {
return u != -1;
}
};
Iterator iterator(int u, int v) {
return Iterator(this, u, v);
}
};
struct SegmentTree {
vector<ll> seg, lazy, weight, wsum;
int size;
SegmentTree(int n) {
size = 1;
while (size < n) size *= 2;
seg.resize(size * 2);
lazy.resize(size * 2);
weight.resize(size);
}
void set(int k, ll v, ll w) {
seg[k + size - 1] = v;
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 push(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) {
push(k, l, r);
if (r <= a || b <= l) return;
if (a <= l && r <= b) {
lazy[k] = v;
push(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) {
push(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);
}
};
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]);
HL hl(N);
rep (i, N - 1) {
int a, b;
cin >> a >> b;
a--; b--;
hl.add(a, b);
}
hl.build();
SegmentTree tr(N);
rep (i, N) {
tr.set(hl.vid[i], S[i], C[i]);
}
tr.build();
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--;
auto it = hl.iterator(x, y);
while (it.has_next()) {
auto p = it.next();
tr.update(p.first, p.second, z);
}
} else {
int x, y;
scanf("%d%d", &x, &y);
x--; y--;
auto it = hl.iterator(x, y);
ll ans = 0;
while (it.has_next()) {
auto p = it.next();
ans += tr.query(p.first, p.second);
ans %= mod;
}
printf("%d\n", (int)ans);
}
}
}