Như những bài chia căn thường lệ, đặt S=√n. Gọi một đỉnh là đỉnh **nặng** nếu như
số cạnh nối với nó lớn hơn S. Định nghĩa đỉnh **nhẹ** tương tự.
Khi thực hiện thao tác cập nhật trên một đỉnh nặng, nếu ta duyệt qua tất cả các đỉnh kề
với nó thì độ phức tạp dễ thổi phồng lên O(n). Vậy thay vào đó, với mỗi đỉnh
nặng u, ta chỉ lưu lại lazy[u] - giá trị truyền cho các đỉnh kề với u.
Còn khi cập nhật trên một đỉnh nhẹ, nếu ta duyệt qua các đỉnh kề với nó thì tổng số đỉnh
được duyệt không vượt quá O(√n). Với những đỉnh kề này, ta lưu lại val[v] -
giá trị thực sự được cập nhật từ những đỉnh kề với v.
Câu trả lời cho mỗi truy vấn là val[u]+∑lazy[v], với v là các đỉnh nặng kề với u.
Trong công thức này, val[u] bao gồm các giá trị được cập nhật từ các đỉnh nhẹ kề với u,
còn lazy[v] bao gồm các đỉnh nặng kề với u.
Ta chứng minh được số đỉnh nặng kề với một đỉnh bất kì không thể vượt quá O(√n).
Vậy, độ phức tạp của xử lý truy vấn là O(q×√n).
Code mẫu:
cpp#∈clude<bitsstdc++.h>#def∈elllonglong#def∈edebug(x)cout〈#x〈 = 〈x〈′n′#def∈eall(a)a.beg∈(),a.end()usingnamespacestd;const∫mxn=1e5+3;const∫mod
Ta sẽ chia căn trên số truy vấn loại 1, đặt B = \sqrt{\frac{N}{\log{N}}}
Gọi add(u) là tổng được thêm vào các cạnh kề u mà chưa được xử lý.
Khi gặp truy vấn loại 2, ta sẽ duyệt qua tất cả các truy vấn loại 1 chưa được xử lý và xem cạnh v hiện tại có kề nhau với cạnh u nào chưa xử lý không, việc này có thể xử lý trong \log(n) bằng set. Nếu có, thêm 1 lượng add(u) vào đáp án.
Cứ mỗi B truy vấn loại 1, ta sẽ duyệt hết truy vấn chưa được xử lý và thêm 1 lượng add(u) vào các cạnh kề.
Tổng độ phực tạp: \mathcal{O}(q \times B \times \log{N}) = \mathcal{O}(q \times \sqrt{\frac{N}{\log{N}}} \times \log{N}) = \mathcal{O}(q \times \sqrt{N \log{N}})
**Code tham khảo:**
cpp
#include "bits/stdc++.h"
using namespace std;
int main() {
cin.tie(0)->sync_with_stdio(0);
int n, q;
cin >> n >> q;
vector<set<int>> g(n);
for (int i = 1; i < n; i++) {
int u, v;
cin >> u >> v;
--u; --v;
g[u].insert(v);
g[v].insert(u);
}
vector<int64_t> c(n);
map<int, int64_t> add;
const int block_size = 80;
auto process = [&]() {
for (auto &it : add) {
for (int u : g[it.first]) {
c[u] += it.second;
}
}
add.clear();
};
for (int i = 0; i < q; i++) {
if (add.size() % block_size == 0) {
process();
}
int t, u;
cin >> t >> u;
--u;
if (t == 1) {
int d; cin >> d;
add[u] += d;
} else {
int64_t res = c[u];
for (auto &it : add)
if (g[u].count(it.first))
res += it.second;
cout << res << '\n';
}
}
}
tuongll
Created at
23 likes
bean
Created at
7 likes