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 (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
5 likes