**Nhận xét:** mọi đỉnh trên đường đi cần truy vấn đều đã hoặc sẽ được _"tô màu"_ (được gán giá trị), đồng thời không bao giờ _"mất màu"_ (đưa giá trị về $0$, do $z\neq0$).
Với mỗi đỉnh, ta lưu lại $par[u]=v$, với $v$ là tổ tiên gần nhất của $u$ mà không được tô trong cùng truy vấn với $u$.
Để thực hiện truy vấn, ta bắt đầu từ đỉnh $y$ và liên tục nhảy lên $par[y]$ ($y$ gán bằng $par[y]$) trong khi độ cao của $y$ còn lớn hơn $x$ (nói cách khác, nhảy theo thứ tự $y,par[y],par[par[y]],...$) và cập nhật các đỉnh có giá trị khác $0$.
Lưu lại các đỉnh $u$ mà ta nhảy tới, khi đã thực hiện xong bước trên cập nhật lại $par[u]$ gán bằng $par[x]$.
Dựa vào nhận xét trên, các đỉnh được truy cập tổng cộng không quá $O(n)$ lần trong mọi truy vấn, vậy độ phức tạp thời gian của thuật toán là $O(n+q)$.
Code mẫu:
```cpp
#include <bits/stdc++.h>
#define ll long long
#define all(a) a.begin(), a.end()
using namespace std;
const int mxn = 1e5 + 3;
const int mod = 1e9 + 7;
const int inf32 = 2e9;
const ll inf64 = 7e18;
int n, q, a[mxn], par[mxn], h[mxn];
vector<int> g[mxn];
void dfs(int u, int pre){
for (int v : g[u]) if (v != pre){
h[v] = h[u] + 1;
par[v] = u;
dfs(v, u);
}
}
void solve(){
cin >> n >> q;
for (int i = 1, u, v; i <= n - 1; ++i){
cin >> u >> v;
g[u].push_back(v), g[v].push_back(u);
}
dfs(1, 0);
while(q--){
int u, v, val;
cin >> u >> v >> val;
vector<int> nodes;
while(h[v] > h[u]){
if (a[v] == 0) a[v] = val;
nodes.push_back(v);
v = par[v];
}
if (a[u] == 0) a[u] = val;
for (int v : nodes){
par[v] = par[u];
}
}
for (int i = 1; i <= n; ++i)
cout << a[i] << ' ';
cout << '\n';
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
solve();
return 0;
}
```
tuongll
Created at
16 likes