# Vấn đề
Cách duyệt trâu: duyệt từ $u \to v$, cập nhật trực tiếp từng đỉnh. Điều này tốn $O(n)$ cho mỗi truy vấn,
tổng $O(qn)$.
Quá lớn với $q, n \leq 10^5$.
Do đó ta tối ưu bằng Binary Lifting + LCA.
Đầu tiên ta tạo bảng `up` bằng binary lifting để tìm $\text{LCA}(u, v)$ trong $O(\log n)$.
## Thay vì duyệt trực tiếp, ta:
- Cập nhật từ $u \to \text{LCA}(u, v)$
- Cập nhật từ $v \to \text{LCA}(u, v)$
- Cộng $w$ thêm 1 lần cho đỉnh chung
## Độ phức tạp
- Duyệt DFS + build `up[][]`: $O(n \log n)$
- Mỗi truy vấn: $O(\log n)$
- Tổng: $O((n + q) \log n)$
---
## Code minh hoạ
```cpp
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn = 1e5 + 5;
const int l = 17;
vector<int> gr[maxn];
bool vis[maxn];
int up[maxn][l];
vector<ll> answ(maxn, 0);
int dep[maxn];
// DFS
void dfs(int u, int p) {
vis[u] = true;
up[u][0] = p;
for (int i = 1; i < l; i++) {
up[u][i] = up[up[u][i - 1]][i - 1];
}
for (int v : gr[u]) {
if (!vis[v]) {
dep[v] = dep[u] + 1;
dfs(v, u);
}
}
}
// Find LCA
int find_lca(int u, int v) {
if (dep[u] < dep[v]) swap(u, v);
for (int i = l - 1; i >= 0; i--) {
if (dep[u] - (1 << i) >= dep[v]) {
u = up[u][i];
}
}
if (u == v) return u;
for (int i = l - 1; i >= 0; i--) {
if (up[u][i] != up[v][i]) {
u = up[u][i];
v = up[v][i];
}
}
return up[u][0];
}
// Update
void update(int u, int res, ll w) {
while (u != res) {
answ[u] += w;
u = up[u][0];
}
}
// Main
int main() {
int n, q;
cin >> n >> q;
for (int i = 0; i < n - 1; i++) {
int u, v;
cin >> u >> v;
gr[u].push_back(v);
gr[v].push_back(u);
}
memset(vis, false, sizeof(vis));
memset(dep, 0, sizeof(dep));
dfs(1, 0);
while (q--) {
int u, v;
ll w;
cin >> u >> v >> w;
int res = find_lca(u, v);
update(u, res, w);
update(v, res, w);
answ[res] += w;
}
for (int i = 1; i <= n; i++) cout << answ[i] << " ";
}
kiennosad
Created at
0 likes