Xét thuật toán sau: ta chạy trâu việc tính kết quả của mọi truy vấn, và lưu lại kết quả
cho các cặp $(x, y)$ đã duyệt qua. Vậy, độ phức tạp của thuật toán này là bao nhiêu?
Trước tiên, ta thấy rằng độ phức tạp dựa vào tổng số cặp $(x, y)$ mà ta duyệt qua trong tất
cả các truy vấn. Đặt $cnt[d]$ là số đỉnh có độ sâu $d$, đóng góp của các cặp ở độ sâu $d$
vào tổng trên là $\min(cnt[d]^2, n)$ (cho tiện, ta thay $q=n$). Khi này, dễ thấy rằng với
$cnt[d]>\sqrt{n}$, đóng góp vào tổng sẽ bằng với khi $cnt[d]=\sqrt{n}$; vì thế, trong
trường hợp tệ nhất thì mọi $cnt[d]\le\sqrt{n}$.
Vậy độ phức tạp bây giờ là $O(\sum cnt[d]^2)$. Giá trị lớn nhất của biểu thức này là
$O(n\sqrt{n})$, khi $cnt[d]=\sqrt{n}$ với mọi $d$.
Về cách lưu lại kết quả cho các cặp $(x,y)$, thật ra ta không cần dùng `std::map` hay bảng
băm gì cả, mà có thể lưu trong một mảng độ lớn $O(n\sqrt{n})$. Nói cách khác, ta chỉ lưu
lại với các độ sâu có $cnt[d]\le\sqrt{n}$, do chỉ có bé hơn $\sqrt{n}$ độ sâu có
$cnt[d]>\sqrt{n}$, và điều đó không ảnh hưởng gì đến độ phức tạp của thuật toán.
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 ll mod = 1e9 + 7;
const int inf32 = 2e9;
const ll inf64 = 7e18;
const int B = 320;
int n, q;
vector<int> g[mxn];
int par[mxn];
int dep[mxn], ord[mxn], cnt[mxn];
ll a[mxn], ans[mxn][B + 1];
void dfs(int u, int d){
ord[u] = ++cnt[d], dep[u] = d;
for (int v : g[u])
dfs(v, d + 1);
}
ll query(int u, int v){
if (!u) return 0;
if (cnt[dep[u]] <= B && ans[u][ord[v]]) return ans[u][ord[v]];
ll res = query(par[u], par[v]) + a[u] * a[v];
if (cnt[dep[u]] <= B) ans[u][ord[v]] = res;
return res;
}
void solve(){
cin >> n >> q;
for (int i = 1; i <= n; ++i)
cin >> a[i];
for (int i = 2; i <= n; ++i){
cin >> par[i];
g[par[i]].push_back(i);
}
dfs(1, 0);
while(q--){
int u, v;
cin >> u >> v;
cout << query(u, v) << '\n';
}
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
solve();
return 0;
}
```
tuongll
Created at
0 likes