結果
| 問題 | No.235 めぐるはめぐる (5) |
| ユーザー |
 lorent_kyopro
|
| 提出日時 | 2021-03-21 23:51:26 |
| 言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 6,565 bytes |
| コンパイル時間 | 2,943 ms |
| コンパイル使用メモリ | 229,216 KB |
| 実行使用メモリ | 31,988 KB |
| 最終ジャッジ日時 | 2024-11-22 19:09:52 |
| 合計ジャッジ時間 | 9,317 ms |
|
ジャッジサーバーID （参考情報） |
judge2 / judge3 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | WA | - |
| testcase_01 | WA | - |
| testcase_02 | WA | - |
ソースコード
#include <bits/stdc++.h>
#include <atcoder/lazysegtree>
#include <atcoder/modint>
__attribute__((constructor))
void fast_io() {
std::ios_base::sync_with_stdio(false);
std::cin.tie(nullptr);
}
class heavy_light_decomposition {
public:
heavy_light_decomposition(size_t n)
: n(n),
tree(n),
subtree_size(n, 1),
parent(n),
in(n),
out(n),
chain_head(n),
built(false) {}
heavy_light_decomposition(const std::vector<std::vector<size_t>>& tree)
: heavy_light_decomposition(tree, 0) {}
heavy_light_decomposition(const std::vector<std::vector<size_t>>& tree,
size_t root)
: n(tree.size()),
tree(tree),
subtree_size(n, 1),
parent(n),
in(n),
out(n),
chain_head(n),
built(false) {
assert(root < n);
build(root);
}
void add_edge(size_t u, size_t v) {
assert(u < n && v < n);
tree[u].push_back(v);
tree[v].push_back(u);
}
void build(size_t root = 0) {
dfs_for_size(0, n);
size_t time = 0;
chain_head[root] = root;
dfs_for_hld(root, time);
built = true;
}
size_t operator[](size_t u) const {
assert(built && u < n);
return in[u];
}
size_t lca(size_t u, size_t v) const {
assert(built && u < n && v < n);
while (true) {
if (in[u] > in[v]) std::swap(u, v);
if (chain_head[u] == chain_head[v]) return u;
v = parent[chain_head[v]];
}
}
std::pair<size_t, size_t> subtree_query(size_t u) const {
assert(built && u < n);
return {in[u], out[u]};
}
template <typename F> void subtree_query(size_t u, const F& f) const {
assert(built && u < n);
f(in[u], out[u]);
}
// when operation is noncommutative
// S resl = e(), resr = e();
// size_t w = hld.lca(u, v)
// hld.node_query(u, w, [&](size_t l, size_t r) { resl = op(resl, rseg.prod(l, r)); });
// hld.edge_query(w, v, [&](size_t l, size_t r) { resr = op(seg.prod(l, r), resr); });
// S res = op(resl, resr);
std::vector<std::pair<size_t, size_t>> node_query(size_t u, size_t v) const {
assert(built && u < n && v < n);
std::vector<std::pair<size_t, size_t>> result;
while (true) {
if (in[u] > in[v]) std::swap(u, v);
if (chain_head[u] != chain_head[v]) {
result.emplace_back(in[chain_head[v]], in[v] + 1);
v = parent[chain_head[v]];
} else {
result.emplace_back(in[u], in[v] + 1);
return result;
}
}
}
template <typename F> void node_query(size_t u, size_t v, const F& f) const {
assert(built && u < n && v < n);
while (true) {
if (in[u] > in[v]) std::swap(u, v);
if (chain_head[u] != chain_head[v]) {
f(in[chain_head[v]], in[v] + 1);
v = parent[chain_head[v]];
} else {
f(in[u], in[v] + 1);
return;
}
}
}
std::vector<std::pair<size_t, size_t>> edge_query(size_t u, size_t v) const {
assert(built && u < n && v < n);
std::vector<std::pair<size_t, size_t>> result;
while (true) {
if (in[u] > in[v]) std::swap(u, v);
if (chain_head[u] != chain_head[v]) {
result.emplace_back(in[chain_head[v]], in[v] + 1);
v = parent[chain_head[v]];
} else {
if (u != v) result.emplace_back(in[u] + 1, in[v] + 1);
return result;
}
}
}
template <typename F> void edge_query(size_t u, size_t v, const F& f) const {
assert(built && u < n && v < n);
while (true) {
if (in[u] > in[v]) std::swap(u, v);
if (chain_head[u] != chain_head[v]) {
f(in[chain_head[v]], in[v] + 1);
v = parent[chain_head[v]];
} else {
if (u != v) f(in[u] + 1, in[v] + 1);
return;
}
}
}
private:
const size_t n;
std::vector<std::vector<size_t>> tree;
std::vector<size_t> subtree_size, parent, in, out, chain_head;
bool built;
void dfs_for_size(size_t u, size_t p) {
parent[u] = p;
if (!tree[u].empty() && tree[u].front() == p)
std::swap(tree[u].front(), tree[u].back());
for (size_t& v : tree[u]) {
if (v == p) continue;
dfs_for_size(v, u);
subtree_size[u] += subtree_size[v];
if (subtree_size[v] > subtree_size[tree[u].front()]) {
std::swap(v, tree[u].front());
}
}
}
void dfs_for_hld(size_t u, size_t& time) {
in[u] = time++;
for (size_t& v : tree[u]) {
if (v == parent[u]) continue;
chain_head[v] = (v == tree[u].front() ? chain_head[u] : v);
dfs_for_hld(v, time);
}
out[u] = time;
}
};
using mint = atcoder::modint1000000007;
using S = std::pair<mint, mint>;
S op(S a, S b) { return {a.first + b.first, a.second + b.second}; }
S e() { return {0, 0}; }
using F = mint;
S mapping(F f, S x) { return {x.first + f * x.second, x.second}; }
F composition(F f, F g) { return f == 0 ? g : f * g; }
F id() { return 0; }
int main() {
size_t n;
std::cin >> n;
std::vector<int> s(n), c(n);
for (auto& si : s) std::cin >> si;
for (auto& ci : c) std::cin >> ci;
heavy_light_decomposition hld(n);
for (size_t i = 0; i < n - 1; ++i) {
size_t u, v;
std::cin >> u >> v;
u--; v--;
hld.add_edge(u, v);
}
hld.build();
std::vector<S> init(n);
for (size_t i = 0; i < n; ++i) init[hld[i]] = {s[i], c[i]};
atcoder::lazy_segtree<S, op, e, F, mapping, composition, id> seg(init);
size_t q;
std::cin >> q;
while (q--) {
int type, z;
size_t x, y;
std::cin >> type;
if (type == 0) {
std::cin >> x >> y >> z;
x--; y--;
hld.node_query(x, y, [&](size_t l, size_t r) { seg.apply(l, r, z); });
} else {
std::cin >> x >> y;
x--; y--;
mint ans = 0;
hld.node_query(x, y, [&](size_t l, size_t r) { ans += seg.prod(l, r).first; });
std::cout << ans.val() << '\n';
}
}
}