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;
}
```
tuongll
Created at
15 likes