Subtask 1 (15%): \(N \le 15, Q=1\)

\(q=1\), gọi u là nhân viên ở giả định ta cần tính.

Sinh nhị phân để chọn ra các nhân viên trong cây con gốc \(u\), sau đó kiểm tra trong \(O(n^2)\).

Độ phức tạp: \(O(2^n * n^2)\).

Subtask 2 (20%): nếu \(u\) là quản lý của \(v\) thì \(a_u > a_v\)

Do mọi nhân viên cấp trên đều có tiền lương lớn hơn nhân viên cấp dưới nên bài toán quy về với mỗi cây con gốc \(u\), ta đếm số đỉnh trong đó.

Độ phức tạp: \(O(n)\).

Subtask 3 (15%): \(i\) là quản lý của \(i+1\) \((1 \le i \le N-1)\)

Cây lúc này quy về một dãy từ \(1\) tới \(n\).

Gọi \(res[u]\) là kết quả nếu giả định ở đỉnh \(u\).

Duyệt từ \(n\) về \(1\), bài toán trở thành LIS. Ta có \(res[u] = max (res[u-1], l[u])\), với \(l[u]\) là độ dài LIS kết thúc tại \(u\) (lưu ý duyệt từ cuối về).

Subtask 4 (15%): \(N \le 1000, a_i \le 100\)

Gọi \(dp[u][i]\) là số đỉnh tối đa có thể chọn trong cây con gốc \(u\) và chúng đều có trọng số nhỏ hơn hoặc bằng \(i\).

Giả sử ta không lấy đỉnh \(u\) vào tập: \(dp[u][i] = dp[u][i] + dp[v][j]\) với \(v\) là con của \(u\) và \(j \le i\)

Nếu lấy đỉnh \(u\) vào tập: \(dp[u][i] = dp[u][i] + dp[v][j] +1\) với \(i = a_u\) và \(j < i\).

Độ phức tạp: \(O(n * max\{a_i\}^2)\).

Subtask 5 (20%): \(N \le 10^5, a_i \le 100\)

Làm tương tự Subtask 4 nhưng cải tiến bằng mảng tiền tố \(max\).

Subtask 6 (15%): Không có ràng buộc gì thêm

Phát triển từ Subtask 3, thấy đây là một bài toán LIS, nhưng là LIS trên cây.

Tương tự với thuật toán tìm LIS. trên mảng, ta cần chọn ra được một tập là tập ứng cử.

Ta sẽ duyệt cây theo thứ tự DFS, xét nút con trước nút cha. Với mỗi nút con, ta lưu trữ thêm một tập ứng cử (dùng multiset).

Đối với các nút con \(v\) của \(u\), do chúng không có quan hệ tổ tiên gì với nhau, nên ta có thể hợp nhất tất cả các tập của chúng lại.

Sau khi hợp nhất, tập chỉ còn thiếu chưa xét đỉnh \(u\) để hoàn thiện tập kết quả của đỉnh \(u\). Lúc này, ta sẽ xử lí giống thuật toán tìm LIS, nếu \(a_u\) lớn hơn toàn bộ các phần tử trong tập, ta thêm \(a_u\) vào tập, ngược lại ta loại bỏ giá trị nhỏ nhất mà vẫn lớn hơn hoặc bằng \(a_u\) trong tập, sau đó thêm \(a_u\) vào. Như vậy, sau thao tác này, tập chỉ có tăng hoặc giữ nguyên chứ không giảm phần tử.

Đáp án của đỉnh \(u\) chính là độ lớn của tập.

Vấn đề bây giờ là làm sao để hợp tập lại cho hiệu quả. Ta có thể sử dụng kĩ thuật Small To Large, chỉ duyệt để hợp tập bé hơn vào tập lớn.

Độ phức tạp: \(O(n * (\log{n})^2)\).

Code tham khảo

#include<bits/stdc++.h>
using namespace std;
const int N = 2e5+5;
vector<int> adj[N];
int a[N];
int n,q;
multiset<int> s[N];
int res[N];
void join (multiset<int> &a, multiset<int> &b) {
    if (a.size() < b.size()) swap (a,b);
    for (multiset<int> ::iterator it = b.begin(); it!=b.end(); it++) a.insert(*it);
}
void dfs (int u, int p){
    for (int i=0; i<adj[u].size(); i++) {
        int v = adj[u][i];
        if (v == p) continue;
        dfs (v,u);
        join (s[u],s[v]);
    }
    if (s[u].size() == 0) s[u].insert(a[u]);
    else {
        if (a[u] > *s[u].rbegin()) s[u].insert(a[u]);
        else {
            s[u].erase(s[u].lower_bound(a[u]));
            s[u].insert(a[u]);
        }
    }
    res[u] = s[u].size();
    //cout << u << ' ' << res[u] << " ??\n";
}
int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    freopen("congty.inp", "r", stdin);
    freopen("congty.out", "w", stdout);
    cin >> n >> q;
    for (int i=1; i<=n; i++) {
        cin >> a[i];
        a[i] = a[i];
    }
    for (int i=2; i<=n; i++) {
        int x; cin >> x;
        adj[x].push_back(i);
    }
    dfs (1,1);
    while (q--) {
        int u; cin >> u;
        cout << res[u] << endl;
    }
}