結果
| 問題 | No.235 めぐるはめぐる (5) |
| ユーザー |
 rpy3cpp
|
| 提出日時 | 2017-10-12 01:19:05 |
| 言語 | C++14 (gcc 13.2.0 + boost 1.83.0) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 11,899 bytes |
| コンパイル時間 | 2,880 ms |
| コンパイル使用メモリ | 193,080 KB |
| 実行使用メモリ | 74,784 KB |
| 最終ジャッジ日時 | 2023-08-10 23:18:53 |
| 合計ジャッジ時間 | 8,296 ms |
|
ジャッジサーバーID （参考情報） |
judge12 / judge15 |
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | WA | - |
| testcase_01 | AC | 881 ms
74,784 KB |
| testcase_02 | WA | - |
ソースコード
// Heavy Light Decomposition
//
// Supports the following operations on tree with weighted vertexes.
// Assign/add a value to a vertex. O(log(n))
// Assign/add a value to a subtree. O(log(n))
// Assign/add a value to a path. O(log(n)^2)
// Get a value of a vertex. O(log(n))
// Get sum of the values of a subtree. O(log(n))
// Get sum of the values of a path. O(log(n)^2)
#include <bits/stdc++.h>
using namespace std;
using vvi = vector<vector<int>>;
constexpr long long mod = 1e9+7;
template<typename T>
struct LazyData {
T add;
T assign;
bool has_assign;
LazyData(T v = 0, T w = 0, bool tf = false) : add(v), assign(w), has_assign(tf) {}
};
template<typename T>
class SegTree {
size_t n;
int h;
vector<T> data; // data[i]: 区間i の重みづけ合計
vector<T> weight; // weight[i]: 区間i の重み
vector<LazyData<T>> lazy; // lazy[i]: 区間i の未伝搬の遅延評価データ
static T combine(T L, T R) { return (L + R) % mod; }
void apply(size_t i, T v, int command_type) {
if (command_type == 0) {
apply_assign(i, v);
} else {
apply_add(i, v);
}
}
void apply_assign(size_t i, T v) { // v: value to assign
data[i] = (weight[i] * v) % mod;
if (i < n) {
lazy[i].add = 0;
lazy[i].assign = v;
lazy[i].has_assign = true;
}
}
void apply_add(size_t i, T v) {
data[i] = (data[i] + (weight[i] * v) % mod) % mod;
if (i < n) {
if (lazy[i].has_assign) {
lazy[i].assign = (lazy[i].assign + v) % mod;
} else {
lazy[i].add = (lazy[i].add + v) % mod;
}
}
}
void build(size_t i) { // update all the parents of node i.
while (i >>= 1) if (not lazy[i].has_assign) data[i] = combine(combine(data[i * 2], data[i * 2 + 1]), (lazy[i].add * weight[i]) % mod);
}
void push(size_t p) { // propagates the changes from the root to node p.
for (int s = h; s > 0; --s) {
size_t i = p >> s;
if (lazy[i].has_assign) {
apply_assign(i * 2, lazy[i].assign);
apply_assign(i * 2 + 1, lazy[i].assign);
lazy[i].has_assign = false;
} else if (lazy[i].add != 0) {
apply_add(i * 2, lazy[i].add);
apply_add(i * 2 + 1, lazy[i].add);
lazy[i].add = 0;
}
}
}
int calc_h(size_t nn) {
int hh = 1;
for (; nn > 1; ++hh, nn >>= 1);
return hh;
}
void process_command(size_t L, size_t R, T v, int command_type) {
L += n;
R += n;
size_t L0 = L;
size_t R0 = R;
push(L);
push(R - 1);
for (; L < R; L >>= 1, R >>= 1) {
if (L & 1) apply(L++, v, command_type);
if (R & 1) apply(--R, v, command_type);
}
build(L0);
build(R0 - 1);
}
void fill_weight(const vector<T> &ws) {
copy(begin(ws), end(ws), begin(weight) + n);
for (int i = n - 1; i > 0; --i) weight[i] = combine(weight[i * 2], weight[i * 2 + 1]);
}
public:
SegTree() : n(0), h(1), data(), weight(), lazy() {}
explicit SegTree(const vector<T> &_weight) : n(_weight.size()), h(calc_h(n)), data(2 * n, 0), weight(2 * n, 0),
lazy(n) {
fill_weight(_weight);
}
SegTree(const vector<T> &src, const vector<T> &_weight) : n(src.size()), h(calc_h(n)), data(2 * n, 0),
weight(2 * n, 0), lazy(n) {
fill_weight(_weight);
for (int i = 0; i < n; ++i) data[n + i] = (src[i] * weight[n + i]) % mod;
for (int i = n - 1; i > 0; --i) data[i] = combine(data[i * 2], data[i * 2 + 1]);
}
void init(const vector<T> &_src, const vector<T> &_weight) {
n = _weight.size();
h = calc_h(n);
data.assign(2 * n, 0);
for (int i = 0; i < n; ++i) data[n + i] = _src[i]; // _src[i] * _weight[i] としていない点に注意。
for (int i = n - 1; i > 0; --i) data[i] = combine(data[i * 2], data[i * 2 + 1]);
weight.assign(2 * n, 0);
lazy.resize(n);
fill_weight(_weight);
}
void modify(size_t L, size_t R, T w) { process_command(L, R, w, 0); } // assign w to range [L, R)
void add(size_t L, size_t R, T v) { process_command(L, R, v, 1); } // add v to range [L, R)
T query(size_t L, size_t R) {
L += n;
R += n;
push(L);
push(R - 1);
T ret = 0;
for (; L < R; L >>= 1, R >>= 1) {
if (L & 1) ret = combine(ret, data[L++]);
if (R & 1) ret = combine(data[--R], ret);
}
return ret;
}
};
class RMQidx {
private:
int n; // size of val
vvi idx; // doubling range min index. idx[k][p]: index of min(val[p:p+2^k]) including p and not including p+2^k.
vector<int> val;
void init(const vector<int> &src) {
n = src.size();
val = src;
idx.emplace_back(vector<int>(n, 0));
for (int i = 0; i != n; ++i) idx[0][i] = i;
for (int k = 0, r = 1; r < n; ++k, r <<= 1) {
idx.emplace_back(idx[k]);
for (int p = 0; p + r < n; ++p) {
auto idxL = idx[k][p];
auto idxR = idx[k][p + r];
idx[k + 1][p] = (val[idxL] > val[idxR]) ? idxR : idxL;
}
}
}
public:
RMQidx() : n(0), idx(vvi()), val(vector<int>()) {}
RMQidx(const vector<int> &src) { init(src); }
int query(int L, int R) { // index of min(data[0][L..R] including both ends. [L, R]
assert(L <= R);
if (L == R) return L;
int k = 31 - __builtin_clz(R - L);
auto idxL = idx[k][L];
auto idxR = idx[k][R + 1 - (1 << k)];
return (val[idxL] > val[idxR]) ? idxR : idxL;
}
};
class LCA {
private:
int n; // number of vertexes
int root;
vector<int> height; // height[v] = height of vertex v.
vector<int> i2v; // i2v[i] = v. Euler tour order of vertexes.
vector<int> v2i; // v2i[v] = i. Last position of vertex v in the Euler tour.
RMQidx rmq; // Range Minimum Query object which returns the position (idx) of the minimum value in the euler tour.
void dfs(int v, int h, const vvi &Es) {
height[v] = h;
i2v.push_back(v);
for (auto u : Es[v]) {
if (height[u] == -1) {
dfs(u, h + 1, Es);
i2v.push_back(v);
}
}
}
public:
LCA(const vvi &Es, int _root = 0) : n(Es.size()), root(_root), height(n, -1), i2v(), v2i(n, -1) {
dfs(root, 0, Es);
assert(i2v.size() == 2 * n - 1);
vector<int> val(2 * n - 1);
for (int i = 0; i != 2 * n - 1; ++i) {
val[i] = height[i2v[i]];
v2i[i2v[i]] = i;
}
rmq = RMQidx(val);
}
int query(int u, int v) {
// returns lowest common ancestor of vertex u and vertex v.
int i = v2i[u];
int j = v2i[v];
if (i > j) swap(i, j);
return i2v[rmq.query(i, j)];
}
};
class HLDecompose {
int n; // number of vertexes
vector<int> subtree_size; // sizes of subtrees
void dfs0(int v, const vvi &Es) {
subtree_size[v] = 1;
for (auto u : Es[v]) {
if (u == parent[v]) continue;
parent[u] = v;
dfs0(u, Es);
subtree_size[v] += subtree_size[u];
}
}
int find_heavy_edge(int v, const vvi &Es) {
int heavy = v;
for (auto u : Es[v]) if (u != parent[v] and (subtree_size[u] > subtree_size[heavy] or heavy == v)) heavy = u;
return heavy;
}
int dfs1(int v, int c, int r, const vvi &Es) {
first[v] = c;
head[v] = r;
int heavy = find_heavy_edge(v, Es);
if (heavy != v) c = dfs1(heavy, c + 1, r, Es);
for (auto u : Es[v]) if (u != parent[v] and u != heavy) c = dfs1(u, c + 1, u, Es);
last[v] = c;
return c;
}
public:
vector<int> parent, first, last, head;
HLDecompose(const vvi &Es) : n(Es.size()), subtree_size(n, 0), parent(n, n), first(n, -1), last(n, -1), head(n, -1) {
dfs0(0, Es);
dfs1(0, 0, 0, Es);
}
};
class HLDSeg {
int n;
LCA lca;
vector<int> parent, first, last, head;
SegTree<long long> seg;
void init_seg(const vector<long long> &src, const vector<long long> &ws) {
assert(ws.size() == n);
vector<long long> vals(n + 1, 0);
for (int i = 0; i < src.size(); ++i) vals[first[i]] = src[i];
vector<long long> weights(n + 1, 0); // n + 1 個目の要素は、root の親を表すダミー頂点
for (int i = 0; i < ws.size(); ++i) weights[first[i]] = ws[i];
seg.init(vals, weights);
}
void modify_core(int u, int v, long long x) { // root -> u -> v -> leaf の順序とする。
for (; head[u] != head[v]; v = parent[head[v]]) seg.modify(first[head[v]], first[v] + 1, x);
seg.modify(first[u], first[v] + 1, x);
}
void add_core(int u, int v, long long x) { // root -> u -> v -> leaf の順序とする。
for (; head[u] != head[v]; v = parent[head[v]]) seg.add(first[head[v]], first[v] + 1, x);
seg.add(first[u], first[v] + 1, x);
}
long long query_core(int u, int v) { // root -> u -> v -> leaf の順序とする。
long long ret = 0;
for (; head[u] != head[v]; v = parent[head[v]]) ret = (ret + seg.query(first[head[v]], first[v] + 1)) % mod;
return (ret + seg.query(first[u], first[v] + 1)) % mod;
}
public:
HLDSeg(const vvi &Es, const vector<long long> & src, const vector<long long> &ws) : n(Es.size()), lca(Es), seg() {
HLDecompose hld(Es);
parent = hld.parent;
first = hld.first;
last = hld.last;
head = hld.head;
init_seg(src, ws);
}
void modify_vertex(int v, long long x) { seg.modify(first[v], first[v] + 1, x); }
void add_vertex(int v, long long x) { seg.add(first[v], first[v] + 1, x); }
void modify_subtree(int v, long long x) { seg.modify(first[v], last[v] + 1, x); }
void add_subtree(int v, long long x) { seg.add(first[v], last[v] + 1, x); }
void modify_path(int u, int v, long long x) {
int w = lca.query(u, v);
modify_core(w, u, x);
modify_core(w, v, x);
}
void add_path(int u, int v, long long x) {
int w = lca.query(u, v);
add_core(w, u, x);
add_core(w, v, x);
add_vertex(w, -x);
}
long long query_vertex(int v) { return seg.query(first[v], first[v] + 1); }
long long query_subtree(int v) { return seg.query(first[v], last[v] + 1); }
long long query_path(int u, int v) {
int w = lca.query(u, v);
return ((query_core(w, u) + query_core(w, v)) % mod + mod - query_vertex(w)) % mod;
}
};
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
int N;
cin >> N;
vector<long long> S(N, 0);
for (auto & s : S) cin >> s;
vector<long long> C(N, 0);
for (auto & c : C) cin >> c;
vvi Es(N, vector<int>());
for (int i = 1; i < N; ++i){
int a, b;
cin >> a >> b;
--a;
--b;
Es[a].push_back(b);
Es[b].push_back(a);
}
HLDSeg hldseg(Es, S, C);
int Q;
cin >> Q;
while (Q--){
int p;
cin >> p;
if (p == 0){
int x, y;
long long z;
cin >> x >> y >> z;
hldseg.add_path(x - 1, y - 1, z);
}else{
int x, y;
cin >> x >> y;
cout << hldseg.query_path(x - 1, y - 1) << '\n';
}
}
return 0;
}