H.cpp

#include <bits/stdc++.h>
#define f first
#define s second
#define ll long long
#define pb push_back
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define mp make_pair

using namespace std;

const int MAXN = 1e6 + 5;
const int INF = 1e9 + 7;
const int MOD = 1e9 + 7;

pair <int, int> a[MAXN];
int dp[MAXN];

void dfs(int v){

    left_num[v] = -1;
    right_num[v] = -1;
    if (g[v].size() == 0 && v != 1){
        cnt_child[v] = 1;
        left_num[v] = a[v];
        right_num[v] = a[v];
    }
    for (int to : g[v]){
        dfs(to);
        cnt_child[v] += cnt_child[to];
    }

    int k = g[v].size();
    for (int i = 0; i < k; i++){
        g[v].pb(g[v][i]);
    }
    vector <int> dp(k + k);
    dp[0] = 1;
    for (int i = 1; i < k + k; i++){
        int to1 = g[v][i];
        int to2 = g[v][i - 1];
        if (left_num[to1] - 1 == right_num[to2]){
            dp[i] = dp[i - 1] + 1;
        }
        else{
            dp[i] = 1;
        }
        if (dp[i] == k){
            to1 = g[v][i];
            to2 = g[v][i - k + 1];
            if (cnt_child[v] == right_num[to1] - left_num[to2] + 1){
                left_num[v] = left_num[to2];
                right_num[v] = right_num[to1];
            }
            break;
        }
    }
}

void solve(int Test){

    int n;
    cin >> n;
    for (int i = 2; i <= n; i++){
        cin >> x;
        g[i].pb(x);
    }
    for (int i = 1; i <= n; i++){
        cin >> a[i];
    }

    dfs(1);



}

main() {
    IOS;
    srand(time(0));
    int t = 1;
    cin >> t;
    int T = 1;
    while(t--){
        solve(T);
        T++;
    }
}