Code : Maximize the Root

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

long long inf = 1e15;

class Tree {
  public:
    int n;
    vector<vector<int>> adj;
    vector<long long> a;
    vector<long long> smin;
    // smin[src] is the minimum value when the entire subtree at src is
    // converted into a mega node.
    // Our goal is to keep the mega node as big as possible, so that future
    // operations are not hindered.

  public:
    Tree(int n) {
        this->n = n;
        adj.resize(n);
        a.resize(n);
        smin.resize(n, inf);
    }

    void dfs(int src, int par) {
        long long min_child = inf;
        for (auto child : adj[src]) {
            if (child == par) {
                continue;
            }
            dfs(child, src);
            min_child = min(min_child, smin[child]);
        }

        if (min_child == inf) {
            smin[src] = a[src];
        } else if (a[src] > min_child) {
            smin[src] = min_child;
        } else {
            smin[src] = (a[src] + min_child) / 2;
        }
    }
    void print_answer() {
        long long mn = inf;
        for (auto child : adj[0]) {
            mn = min(mn, smin[child]);
        }
        cout << mn + a[0] << "\n";
    }
};

void solve() {
    int n;
    cin >> n;
    Tree t(n);

    for (int i = 0; i < n; i++) {
        cin >> t.a[i];
    }
    for (int i = 1; i < n; i++) {
        int j;
        cin >> j;
        j--;
        t.adj[i].push_back(j);
        t.adj[j].push_back(i);
    }

    t.dfs(0, -1);
    t.print_answer();
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int t;
    cin >> t;
    for (int zz = 0; zz < t; zz++) {
        solve();
    }
}