Như những bài chia căn thường lệ, đặt $S=\sqrt{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(\sqrt{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]+\sum 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(\sqrt{n})$.
Vậy, độ phức tạp của xử lý truy vấn là $O(q\times \sqrt{n})$.
Code mẫu:
```cpp
#include <bits/stdc++.h>
#define ll long long
#define debug(x) cout << #x << " = " << x << '\n'
#define all(a) a.begin(), a.end()
using namespace std;
const int mxn = 1e5 + 3;
const int mod = 998244353;
const int inf32 = 2e9;
const ll inf64 = 7e18;
int n, q, S, deg[mxn];
ll val[mxn], lazy[mxn];
vector<int> g[mxn], heavy[mxn];
void solve(){
cin >> n >> q;
S = sqrt(n);
for (int i = 1, u, v; i <= n - 1; ++i){
cin >> u >> v;
g[u].push_back(v);
g[v].push_back(u);
++deg[u], ++deg[v];
}
for (int u = 1; u <= n; ++u){
for (int v : g[u]){
if (deg[u] > S || deg[v] > S)
heavy[u].push_back(v);
}
}
while(q--){
int type, u, d;
cin >> type >> u;
if (type == 1){
cin >> d;
if (deg[u] > S) lazy[u] += d;
else for (int v : g[u])
val[v] += d;
}
else {
ll res = val[u];
for (int v : heavy[u])
res += lazy[v];
cout << res << '\n';
}
}
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
solve();
return 0;
}
```
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
17 likes
bean
Created at
1 likes