#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
#define all(x) (x).begin(),(x).end()

template<typename T>
ostream &operator<<(ostream &os, const vector<T> &v) {
    for (int i = 0; i < int(v.size()); i++) cout << v[i] << (i + 1 == int(v.size()) ? "" : " ");
    return os;
}

template<typename T>
ostream &operator<<(ostream &os, const map<T,int> &mp){
  cout << "{";
  for (auto e:mp){
    cout << e.first << ": " << e.second << ", ";
  }
  cout << "}";
  return os;
}

#ifdef LOCAL
#define debug(x) cerr << #x << " = " << (x) << "(L" << __LINE__ << ")" << endl;
#else
#define debug(x)
#endif

template<typename T>
struct SlopeTrick {
    const T inf = numeric_limits<T>::max() / 2;
    T min_f;
    map<T,int> L,R;
    T add_l, add_r;
    T min_cut;
    int merge_size = 0;

    void push_L(const T &a){
      merge_size++;
      if (!L.count(a-add_l)) L[a-add_l] = 0;
      L[a-add_l]++;
    }

    T top_L() const{
      if (L.empty())  return -inf;
      T x = (L.rbegin()->first);
      return x;
    }

    T pop_L() {
      T res = top_L();
      if (!L.empty()){
        merge_size--;
        assert (L[res]);
        L[res]--;
        if (L[res] == 0) L.erase(res);
      }
      return res;
    }

    void push_R(const T &a){
      merge_size++;
      if (!R.count(a-add_r)) R[a-add_r] = 0;
      R[a-add_r]++;
    }

    T top_R() const {
      if (R.empty()) return inf;
      return (R.begin()->first) + add_r;
    }

    T pop_R(){
      T res = top_R();
      if (!R.empty()){
        merge_size--;
        assert (R[res-add_r]);
        R[res-add_r]--;
        if (R[res-add_r] == 0) R.erase(res-add_r);
      }
      return res;
    }

    SlopeTrick() : min_f(0), add_l(0), add_r(0), min_cut(0) {}

    int size() const { return merge_size; }

    void add_a_minus_x(T a) {
        if (min_cut <= a){
          min_f += a - min_cut;
          a = min_cut;
        }
        min_f += max(T(0), a - top_R());
        push_R(a);
        push_L(pop_R());
    }

    void add_x_minus_a(T a) {
        if (min_cut <= a){
          a = min_cut;
        };
        min_f += max(T(0), top_L() - a);
        push_L(a);
        push_R(pop_L());
    }

    void add_min_cut(){
      min_cut++;
    }

    void change_min_cut(T p){
      //cout << "change_min_cut" << " " << min_cut << " " << p << endl;
      if (min_cut <= p) return ;

      while (!R.empty()){
        auto x = (R.rbegin()->first);
        if (x+add_r < p) break;
        R.erase(x);
      }

      int new_min_cut_L = 0;
      while (!L.empty()){
        auto x = (L.rbegin()->first);
        if (x+add_l < p) break;
        min_f += (x+add_l-p) * L[x];
        new_min_cut_L += L[x];
        L.erase(x);
      }
      if (new_min_cut_L){
        if (!L.count(p)) L[p] = 0;
        L[p] += new_min_cut_L;
      }

      min_cut = p;
    }

    void merge_destructive(SlopeTrick &g) {
      //cout << size() << " " << g.size() << endl;
        if (g.size() > size()) {
            swap(min_f, g.min_f);
            swap(L, g.L);
            swap(R, g.R);
            swap(add_l, g.add_l);
            swap(add_r, g.add_r);
            swap(min_cut,g.min_cut);
            swap(merge_size,g.merge_size);
        }
        min_f += g.min_f;
        merge_size += g.merge_size;
        change_min_cut(g.min_cut);
        while (not g.L.empty()) add_a_minus_x(g.pop_L());
        while (not g.R.empty()) add_x_minus_a(g.pop_R());
    }
};


void solve() {
    int n;
    cin >> n;
    string S;
    cin >> S;
    vector<int> p(n);
    for (int i = 1; i < n; i++) cin >> p[i], p[i]--;

    vector<int> ans(n);
    vector<SlopeTrick<int>> ST(n);
    for (int i=0;i<n;i++){
      ST[i].min_cut = n+1;
    }

    vector<vector<int>> fuck_dp(n);

    auto debug_dp = [&](int i){
      vector<int> dp(n+1,ST[i].min_f);
      int p = ST[i].min_cut;
      cout << "## " <<  i << " ## " << dp << endl;
      for (auto a:ST[i].L){
        for (int j=0;j<=p;j++){
          dp[j] += max((a.first-j) * a.second,0);
        }
      }
      cout << "## " <<  i << " ## " << dp << endl;
      for (auto a:ST[i].R){
        for (int j=0;j<=p;j++){
          dp[j] += max((j-(a.first+ST[i].add_r))*a.second,0);
        }
      }
      cout << "## " <<  i << " ## " << dp << endl;
      for (int j=p+1;j<=n;j++){
        dp[j] = n+1;
      }
      fuck_dp[i] = dp;
    };


    for (int i = n - 1; i > 0; i--) {
      //cout << "start " << i << endl;
        if (ST[i].size() == 0) {
            //cout << "init_leaf" << endl;
            ST[i].add_a_minus_x(0);
            ST[i].add_x_minus_a(0);
            ST[i].min_cut = 0;
        }
        ST[i].add_min_cut();
        //cout << S << " " << S[i] << endl;
        if (S[i] == '0') {
            if (not ST[i].R.empty()) {
                int tmp = ST[i].pop_R();
                ST[i].add_r++;
                ST[i].push_R(tmp);
            }
        } else {
            //cout << "SINE" << endl;
            if (!ST[i].L.empty()) {
              //cout << "FUCK" << endl;
                ST[i].push_R(ST[i].pop_L());
                ST[i].add_r++;
                ST[i].push_L(ST[i].pop_R());
            }
        }
        //debug_dp(i);
        //cout << i << endl;
        //cout << ST[i].L << " " << ST[i].R << " " << ST[i].min_cut << " " << ST[i].min_f << endl;
        //cout << ST[i].add_r <<  endl;
        ans[i] = ST[i].min_f;
        ST[p[i]].merge_destructive(ST[i]);
        //cout << ST[p[i]].L << " " << ST[p[i]].R << " " << ST[p[i]].min_cut <<  endl;
    }
    ans[0] = ST[0].min_f;
    //debug_dp(0);

    for (int i=0;i<n;i++){
      //cout << fuck_dp[i] << endl;
    }

    

    cout << ans << "\n";
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T;
    cin >> T;
    for (; T--;) solve();
    return 0;
}