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

typedef long long ll;

// Fast IO setup
struct FastIO {
    FastIO() {
        ios::sync_with_stdio(false);
        cin.tie(nullptr);
    }
};

// Subtask 1: n, q, sum of k <= 1000
void solve_subtask1(int n, int q, 
                    const vector<int>& parents, 
                    vector<int> country, 
                    const vector<long long>& c, 
                    const vector<pair<int, vector<int>>>& queries) {
    // Build tree
    vector<vector<int>> adj(n + 1, vector<int>());
    for(int i = 2; i <= n; ++i){
        adj[parents[i-2]].push_back(i);
    }
    
    // Build country lists
    vector<vector<int>> countries(n + 1, vector<int>());
    for(int i = 1; i <= n; ++i){
        countries[country[i]].push_back(i);
    }
    
    // Process queries
    for(auto &[type, params] : queries){
        if(type == 1){
            int v = params[0];
            int tnew = params[1];
            int told = country[v];
            // Remove v from old country
            auto &vec_old = countries[told];
            vec_old.erase(find(vec_old.begin(), vec_old.end(), v));
            // Add v to new country
            countries[tnew].push_back(v);
            // Update country
            country[v] = tnew;
        }
        else{
            int t = params[0];
            int k = params[1];
            vector<int> treasures(params.begin() + 2, params.end());
            // Mark treasures
            vector<bool> is_treasure(n + 1, false);
            for(auto x: treasures) is_treasure[x] = true;
            // Compute numv using DFS
            vector<long long> numv(n + 1, 0);
            // Recursive DFS
            function<long long(int)> dfs = [&](int u) -> long long{
                long long cnt = is_treasure[u] ? 1 : 0;
                for(auto &v_child: adj[u]){
                    cnt += dfs(v_child);
                }
                numv[u] = cnt;
                return cnt;
            };
            dfs(1);
            // Now iterate over country t
            long long max_tax = 0;
            for(auto v: countries[t]){
                long long tax = c[v] * numv[v];
                if(tax > max_tax) max_tax = tax;
            }
            cout << max_tax << "\n";
        }
    }
}

// Subtask 2: No type 1 queries and ti = 1
void solve_subtask2(int n, int q, 
                    const vector<int>& parents, 
                    const vector<int>& country, 
                    const vector<long long>& c, 
                    const vector<pair<int, vector<int>>>& queries) {
    // Since all countries are 1 and no type 1 queries
    // Preprocess parent array
    vector<int> parent(n + 1, 0);
    for(int i = 2; i <= n; ++i){
        parent[i] = parents[i-2];
    }
    
    // Initialize variables for queries
    vector<int> last_visit(n + 1, 0);
    vector<int> cnt_v(n + 1, 0);
    int current_query_id = 0;
    
    for(auto &[type, params] : queries){
        if(type == 1){
            // No type1 queries in subtask2
            continue;
        }
        else{
            // Type 2 query
            int t = params[0]; // Always 1
            int k = params[1];
            vector<int> treasures(params.begin() + 2, params.end());
            
            current_query_id++;
            ll max_tax = 0;
            
            for(auto a_i: treasures){
                int v = a_i;
                while(v != 0){
                    if(last_visit[v] != current_query_id){
                        cnt_v[v] = 0;
                        last_visit[v] = current_query_id;
                    }
                    cnt_v[v] +=1;
                    ll current_tax = c[v] * (ll)cnt_v[v];
                    if(current_tax > max_tax){
                        max_tax = current_tax;
                    }
                    v = parent[v];
                }
            }
            cout << max_tax << "\n";
        }
    }
}

// Subtask 3: No type 1 queries
void solve_subtask3(int n, int q, 
                    const vector<int>& parents, 
                    const vector<int>& country, 
                    const vector<long long>& c, 
                    const vector<pair<int, vector<int>>>& queries) {
    // Precompute in and out times using Euler Tour
    // Build tree
    vector<vector<int>> adj(n + 1, vector<int>());
    for(int i = 2; i <= n; ++i){
        adj[parents[i-2]].push_back(i);
    }
    
    // Euler Tour
    vector<int> in_order(n + 1), out_order(n + 1);
    int timer = 1;
    // Iterative DFS
    stack<pair<int, int>> stk;
    stk.emplace(1, 0); // node, state
    while(!stk.empty()){
        auto [u, state] = stk.top(); stk.pop();
        if(state == 0){
            in_order[u] = timer;
            timer++;
            stk.emplace(u, 1);
            for(auto it = adj[u].rbegin(); it != adj[u].rend(); ++it){
                stk.emplace(*it, 0);
            }
        }
        else{
            out_order[u] = timer -1;
        }
    }
    
    // Build country lists
    vector<vector<int>> countries(n + 1, vector<int>());
    for(int i = 1; i <= n; ++i){
        countries[country[i]].push_back(i);
    }
    
    // Sort each country's nodes by c_v descendingly
    for(int t = 1; t <= n; ++t){
        if(!countries[t].empty()){
            sort(countries[t].begin(), countries[t].end(), [&](const int a, const int b) -> bool{
                if(c[a] != c[b]) return c[a] > c[b];
                return in_order[a] < in_order[b];
            });
        }
    }
    
    // BIT implementation
    vector<int> BIT_tree(n + 2, 0);
    
    auto update = [&](auto &update_ref, int idx, int delta) -> void{
        while(idx <= n){
            BIT_tree[idx] += delta;
            idx += idx & -idx;
        }
    };
    
    auto query = [&](auto &query_ref, int idx) -> int{
        int res = 0;
        while(idx > 0){
            res += BIT_tree[idx];
            idx -= idx & -idx;
        }
        return res;
    };
    
    // Process queries
    for(auto &[type, params] : queries){
        if(type == 1){
            // No type1 queries in subtask3
            continue;
        }
        else{
            // Type2 query
            int t = params[0];
            int k = params[1];
            vector<int> treasures(params.begin() + 2, params.end());
            
            // Insert treasures into BIT
            for(auto &x: treasures){
                update(update, in_order[x], 1);
            }
            
            // Iterate through t's nodes sorted by c_v descendingly
            ll max_tax = 0;
            for(auto &v: countries[t]){
                // Calculate number of treasures in subtree of v
                int cnt = query(query, out_order[v]) - query(query, in_order[v]-1);
                ll tax = (ll)c[v] * cnt;
                if(tax > max_tax){
                    max_tax = tax;
                }
            }
            
            cout << max_tax << "\n";
            
            // Remove treasures from BIT
            for(auto &x: treasures){
                update(update, in_order[x], -1);
            }
        }
    }
}

// Subtask 4: pi = i -1 (tree is a path)
void solve_subtask4(int n, int q, 
                    const vector<int>& parents, 
                    vector<int> country, 
                    const vector<long long>& c, 
                    const vector<pair<int, vector<int>>>& queries) {
    // Since the tree is a path: 1-2-3-...-n
    // In this tree, in_order is simply the node number
    // No need for Euler Tour
    
    // Build country lists, sorted
    vector<vector<int>> countries(n + 1, vector<int>());
    for(int i = 1; i <= n; ++i){
        countries[country[i]].push_back(i);
    }
    for(int t = 1; t <= n; ++t){
        if(!countries[t].empty()){
            sort(countries[t].begin(), countries[t].end());
        }
    }
    
    for(auto &[type, params] : queries){
        if(type == 1){
            // Type1 query: Change country assignment
            int v = params[0];
            int tnew = params[1];
            int told = country[v];
            if(told != tnew){
                // Remove v from old country
                auto &vec_old = countries[told];
                int pos = lower_bound(vec_old.begin(), vec_old.end(), v) - vec_old.begin();
                if(pos < vec_old.size() && vec_old[pos] == v){
                    vec_old.erase(vec_old.begin() + pos);
                }
                // Add v to new country
                auto &vec_new = countries[tnew];
                vec_new.insert(lower_bound(vec_new.begin(), vec_new.end(), v), v);
                // Update country assignment
                country[v] = tnew;
            }
        }
        else{
            // Type2 query: Compute maximum tax
            int t = params[0];
            int k = params[1];
            vector<int> treasures(params.begin() + 2, params.end());
            sort(treasures.begin(), treasures.end());
            const vector<int> &nodes = countries[t];
            if(nodes.empty()){
                cout << "0\n";
                continue;
            }
            ll max_tax = 0;
            for(auto v: nodes){
                // In a path tree, subtree of v includes nodes v to n
                // Number of treasures >= v
                int numv = treasures.end() - lower_bound(treasures.begin(), treasures.end(), v);
                if(numv > 0){
                    ll tax = c[v] * (ll)numv;
                    if(tax > max_tax){
                        max_tax = tax;
                    }
                }
            }
            cout << max_tax << "\n";
        }
    }
}

// Subtask 5: pi = floor(i/2) (binary tree), with type 1 queries
void solve_subtask5(int n, int q, 
                    const vector<int>& parents, 
                    vector<int> country, 
                    const vector<long long>& c, 
                    const vector<pair<int, vector<int>>>& queries) {
    // Build tree
    vector<vector<int>> adj(n + 1, vector<int>());
    for(int i = 2; i <= n; ++i){
        adj[parents[i-2]].push_back(i);
    }
    
    // Euler Tour
    vector<int> in_order(n + 1), out_order(n + 1);
    int timer = 1;
    // Iterative DFS
    stack<pair<int, int>> stk;
    stk.emplace(1, 0); // node, state
    while(!stk.empty()){
        auto [u, state] = stk.top(); stk.pop();
        if(state == 0){
            in_order[u] = timer;
            timer++;
            stk.emplace(u, 1);
            for(auto it = adj[u].rbegin(); it != adj[u].rend(); ++it){
                stk.emplace(*it, 0);
            }
        }
        else{
            out_order[u] = timer -1;
        }
    }
    
    // Initialize countries: vector of vectors, sorted by in_order
    vector<vector<int>> countries(n + 1, vector<int>());
    for(int i = 1; i <= n; ++i){
        countries[country[i]].push_back(i);
    }
    // Sort each country's nodes by in_order
    for(int t = 1; t <= n; ++t){
        if(!countries[t].empty()){
            sort(countries[t].begin(), countries[t].end(), [&](const int a, const int b) -> bool{
                return in_order[a] < in_order[b];
            });
        }
    }
    
    // To handle dynamic updates, use a BIT for treasures
    vector<int> BIT_tree(n + 2, 0);
    
    auto update_BIT = [&](auto &update_ref, int idx, int delta) -> void{
        while(idx <= n){
            BIT_tree[idx] += delta;
            idx += idx & -idx;
        }
    };
    
    auto query_BIT = [&](auto &query_ref, int idx) -> int{
        int res = 0;
        while(idx > 0){
            res += BIT_tree[idx];
            idx -= idx & -idx;
        }
        return res;
    };
    
    // Process queries
    for(auto &[type, params] : queries){
        if(type == 1){
            // Type1 query: Change country assignment
            int v = params[0];
            int tnew = params[1];
            int told = country[v];
            if(told != tnew){
                // Remove v from old country
                auto &vec_old = countries[told];
                // Binary search to find v based on in_order
                int pos = lower_bound(vec_old.begin(), vec_old.end(), v, [&](const int a, const int b) -> bool{
                    return in_order[a] < in_order[b];
                }) - vec_old.begin();
                // Ensure correct node
                while(pos < vec_old.size() && in_order[vec_old[pos]] == in_order[v] && vec_old[pos] != v){
                    pos++;
                }
                if(pos < vec_old.size() && vec_old[pos] == v){
                    vec_old.erase(vec_old.begin() + pos);
                }
                // Insert v into new country
                auto &vec_new = countries[tnew];
                int insert_pos = lower_bound(vec_new.begin(), vec_new.end(), v, [&](const int a, const int b) -> bool{
                    return in_order[a] < in_order[b];
                }) - vec_new.begin();
                vec_new.insert(vec_new.begin() + insert_pos, v);
                // Update country assignment
                country[v] = tnew;
            }
        }
        else{
            // Type2 query: Compute maximum tax
            int t = params[0];
            int k = params[1];
            vector<int> treasures(params.begin() + 2, params.end());
            // Insert treasures into BIT
            for(auto &x: treasures){
                update_BIT(update_BIT, in_order[x], 1);
            }
            // Iterate through t's nodes sorted by in_order
            ll max_tax = 0;
            for(auto &v: countries[t]){
                // Calculate number of treasures in subtree of v
                int cnt = query_BIT(query_BIT, out_order[v]) - query_BIT(query_BIT, in_order[v]-1);
                ll tax = (ll)c[v] * cnt;
                if(tax > max_tax){
                    max_tax = tax;
                }
            }
            cout << max_tax << "\n";
            // Remove treasures from BIT
            for(auto &x: treasures){
                update_BIT(update_BIT, in_order[x], -1);
            }
        }
    }
}

int main(){
    FastIO fio;
    
    int n, q;
    cin >> n >> q;
    
    // Read parents for the tree
    vector<int> parents(n-1);
    for(auto &p: parents) cin >> p;
    
    // Read initial country assignments
    vector<int> country(n +1);
    for(int i =1; i <=n; ++i) cin >> country[i];
    
    // Read c values
    vector<long long> c(n +1);
    for(int i =1; i <=n; ++i) cin >> c[i];
    
    // Read all queries
    // Each query is a pair: type and parameters
    // For type 1: [v, tnew]
    // For type 2: [t, k, a1, a2, ..., ak]
    vector<pair<int, vector<int>>> queries;
    queries.reserve(q);
    for(int i =0; i < q; ++i){
        int xi;
        cin >> xi;
        if(xi == 1){
            int v, tnew;
            cin >> v >> tnew;
            queries.emplace_back(make_pair(xi, vector<int>{v, tnew}));
        }
        else{
            int t, k;
            cin >> t >> k;
            vector<int> params = {t, k};
            params.reserve(k +2);
            for(int j =0; j < k; ++j){
                int a;
                cin >> a;
                params.push_back(a);
            }
            queries.emplace_back(make_pair(xi, params));
        }
    }
    
    // Determine which subtask to solve based on constraints
    // For demonstration, we'll assume all subtasks are independent
    // and call each solve function separately with relevant constraints
    // In practice, you'd implement a single solution handling all constraints
    
    // Example calls (uncomment the one relevant to your subtask)
    
    // solve_subtask1(n, q, parents, country, c, queries);
    // solve_subtask2(n, q, parents, country, c, queries);
    // solve_subtask3(n, q, parents, country, c, queries);
    // solve_subtask4(n, q, parents, country, c, queries);
    solve_subtask5(n, q, parents, country, c, queries);
    
    return 0;
}

Subtask 1: n, q and sum of all ki <= 1000.
Subtask 2: No query type 1 and ti = 1.
Subtask 3: No query type 1.
Subtask 4: pi = i - 1.
Subtask 5:pi = ⌊ i/2 ⌋  the ⌊ ⌋ is round down.
please help me call each function