Trước hết, ta nhận xét rằng khi nhân viên ~i~ và sếp ~p_i~ cùng đi làm, ta luôn có thể chọn cách sắp xếp sao cho chi phí di chuyển giữa họ là nhỏ nhất, cụ thể là ~\min(a_i, b_i)~. Điều này đảm bảo rằng nếu nhân viên và sếp đều đi làm, ta luôn có cách xếp hàng hợp lý để tối ưu hóa tổng chi phí.

Ta định nghĩa: ~\text{cost}(i) = \min(a_i, b_i)~ là chi phí tối thiểu khi nhân viên ~i~ và sếp của họ cùng đi làm.

Subtask 1: Tổng ~n~ trong mọi test case không vượt quá ~20~.

Ta sẽ chạy toàn bộ trường hợp có thể xảy ra.

Độ phức tạp: ~O(2^n)~

Subtask 2: Cây là một đường thẳng.

Lúc này, ta sẽ suy ra công thức quy hoạch động là

• ~dp0[i][j]~ là tổng số stress nhỏ nhất khi xét nhân viên ~1~ tới nhân viên thứ ~i~ và đã chọn được ~j~ nhân viên đi làm với điều kiện là nhân viên thứ ~i~ không đi làm.

• ~dp0[i][j]~ là tổng số stress nhỏ nhất khi xét nhân viên ~1~ tới nhân viên thứ ~i~ và đã chọn được ~j~ nhân viên đi làm với điều kiện là nhân viên thứ ~i~ đi làm.

$$dp0[i][j] = \min(dp0[i-1][j], dp1[i-1][j])$$ $$dp1[i][j] = \min(dp0[i-1][j-1], dp1[i-1][j-1] + cost[i])$$.

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

Subtask 3:

Khi cây không còn là đường thẳng mà là một cấu trúc tổng quát, ta mở rộng ý tưởng của Subtask 2. Lúc này, mỗi sếp có thể có nhiều nhân viên cấp dưới, do đó ta cần một phương pháp linh hoạt hơn để cập nhật trạng thái quy hoạch động.

Với mỗi đỉnh ~u~, ta cần quy hoạch động cái túi để tìm ra chi phí nhỏ nhất

~\displaystyle dp0[u][j] = \sum_{v}^{}{\min(dp0[v][j_v], dp1[v][j_v])}~ sao cho ~\displaystyle\sum_v{j_v} = j~.

~\displaystyle dp1[u][j] = \sum_{v}^{}{\min(dp0[v][j_v], dp1[v][j_v] + cost(v))}~ sao cho ~\displaystyle\sum_v{j_v} = j-1~.

Và để tối ưu hơn nữa, sau khi duyệt đỉnh ~v~ thì ta có thể cập nhật trạng trái ngay lập tức. Chi tiết xem ở code.

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

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
const ll INF = 1e18;

int n;
vector<int> children[2100];
ll penalty[2100];

pair<vector<ll>, vector<ll>> dfs(int u) {
    vector<ll> dp0(1, 0);
    vector<ll> dp1(2, INF);
    dp1[1] = 0;

    for (int v : children[u]) {
        auto childDP = dfs(v);
        vector<ll> child0 = childDP.first;
        vector<ll> child1 = childDP.second;
        int sz0 = child0.size(), sz1 = child1.size();
        int szChild = max(sz0, sz1);

        vector<ll> contribNotChosen(szChild, INF);
        for (int r = 0; r < szChild; r++) {
            ll cost0 = (r < sz0 ? child0[r] : INF);
            ll cost1 = (r < sz1 ? child1[r] : INF);
            contribNotChosen[r] = min(cost0, cost1);
        }

        vector<ll> contribChosen(szChild, INF);
        for (int r = 0; r < szChild; r++) {
            ll cost0 = (r < sz0 ? child0[r] : INF);
            ll cost1 = (r < sz1 ? child1[r] + penalty[v] : INF);
            contribChosen[r] = min(cost0, cost1);
        }

        int szU0 = dp0.size();
        vector<ll> new_dp0(szU0 + szChild - 1, INF);
        for (int i = 0; i < szU0; i++) {
            for (int j = 0; j < szChild; j++) {
                if(dp0[i] < INF && contribNotChosen[j] < INF)
                    new_dp0[i + j] = min(new_dp0[i + j], dp0[i] + contribNotChosen[j]);
            }
        }
        dp0 = new_dp0;

        int szU1 = dp1.size();
        vector<ll> new_dp1(szU1 + szChild - 1, INF);
        for (int i = 0; i < szU1; i++) {
            for (int j = 0; j < szChild; j++) {
                if(dp1[i] < INF && contribChosen[j] < INF)
                    new_dp1[i + j] = min(new_dp1[i + j], dp1[i] + contribChosen[j]);
            }
        }
        dp1 = new_dp1;
    }
    return {dp0, dp1};
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int t; 
    cin >> t;
    while(t--){
        cin >> n;
        for (int i = 1; i <= n; i++){
            children[i].clear();
        }

        for (int i = 2; i <= n; i++){
            int p;
            cin >> p;
            children[p].push_back(i);
        }

        vector<ll> a(n+1, 0), b(n+1, 0);
        for (int i = 2; i <= n; i++){
            cin >> a[i];
        }
        for (int i = 2; i <= n; i++){
            cin >> b[i];
        }

        for (int i = 2; i <= n; i++){
            penalty[i] = min(a[i], b[i]);
        }
        penalty[1] = 0;

        auto rootDP = dfs(1);
        vector<ll> dp0 = rootDP.first;
        vector<ll> dp1 = rootDP.second;

        vector<ll> ans(n+1, INF);
        for (int m = 1; m <= n; m++){
            if(m < dp0.size())
                ans[m] = min(ans[m], dp0[m]);
            if(m < dp1.size())
                ans[m] = min(ans[m], dp1[m]);
        }

        for (int m = 1; m <= n; m++){
            cout << ans[m] << " ";
        }
        cout << "\n";
    }
    return 0;
}