#if __INCLUDE_LEVEL__ == 0

#include __BASE_FILE__

namespace {

constexpr int INF = INT_MAX / 2;

void solve() {
  int n;
  scan(n);
  string s;
  scan(s);
  vector<int> p(n, -1);
  vector<vector<int>> g(n);
  for (int i : rep(1, n)) {
    scan(p[i]);
    --p[i];
    g[p[i]].push_back(i);
  }

  vector<int> ans(n);
  vector<SlopeTrick> d(n);
  fix([&](auto self, int i) -> void {
    if (g[i].empty()) {
      if (s[i] == '1') {
        d[i].add_amx(1);
      } else {
        d[i].add_xma(0);
      }
      d[i].add_amx(0, INF);
      d[i].add_xma(1, INF);
      return;
    }

    for (int j : g[i]) {
      self(j);
      d[i].merge(d[j]);
    }

    if (s[i] == '1') {
      d[i].shift_x(1);
      const auto tmp = d[i].getL();
      d[i].popL();
      if (1 < tmp.c) {
        d[i].pushL(tmp.x, tmp.c - 1);
      }
      d[i].shift_L(-1);
      d[i].pushL(tmp.x);
    } else {
      const auto tmp = d[i].getR();
      d[i].popR();
      if (1 < tmp.c) {
        d[i].pushR(tmp.x, tmp.c - 1);
      }
      d[i].shift_R(1);
      d[i].pushR(tmp.x);
    }
    ans[i] = d[i].get_min().second;
  })(0);

  print(ans);
}

}  // namespace

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

  int t;
  scan(t);
  while (t--) {
    solve();
  }
}

#else  // __INCLUDE_LEVEL__

#include <bits/stdc++.h>

using namespace std;

template <class T>
concept tuple_like = __is_tuple_like<T>::value && !ranges::range<T>;

template <class R>
concept nstr_range = ranges::range<R> && !convertible_to<R, string_view>;

namespace std {

istream& operator>>(istream& is, tuple_like auto&& t) {
  return apply([&is](auto&... xs) -> istream& { return (is >> ... >> xs); }, t);
}

istream& operator>>(istream& is, nstr_range auto&& r) {
  for (auto&& e : r) {
    is >> e;
  }
  return is;
}

ostream& operator<<(ostream& os, tuple_like auto&& t) {
  auto f = [&os](auto&... xs) -> ostream& {
    [[maybe_unused]] auto sep = "";
    ((os << exchange(sep, " ") << xs), ...);
    return os;
  };
  return apply(f, t);
}

ostream& operator<<(ostream& os, nstr_range auto&& r) {
  auto sep = "";
  for (auto&& e : r) {
    os << exchange(sep, " ") << e;
  }
  return os;
}

#define DEF_INC_OR_DEC(op) \
  auto& operator op(tuple_like auto&& t) { \
    apply([](auto&... xs) { (op xs, ...); }, t); \
    return t; \
  } \
  auto& operator op(nstr_range auto&& r) { \
    for (auto&& e : r) { \
      op e; \
    } \
    return r; \
  }

DEF_INC_OR_DEC(++)
DEF_INC_OR_DEC(--)

#undef DEF_INC_OR_DEC

}  // namespace std

void scan(auto&&... xs) { cin >> tie(xs...); }
void print(auto&&... xs) { cout << tie(xs...) << '\n'; }

template <class F>
class fix {
 public:
  explicit fix(F f) : f_(move(f)) {}

  template <class... Ts>
  decltype(auto) operator()(Ts&&... xs) const {
    return f_(ref(*this), forward<Ts>(xs)...);
  }

 private:
  F f_;
};

using views::drop;
using views::take;
inline constexpr auto rev = views::reverse;
inline constexpr auto len = ranges::ssize;
inline auto rep(int l, int r) { return views::iota(min(l, r), r); }
inline auto rep(int n) { return rep(0, n); }
inline auto rep1(int l, int r) { return rep(l, r + 1); }
inline auto rep1(int n) { return rep(1, n + 1); }

// https://nyaannyaan.github.io/library/data-structure/slope-trick.hpp
struct SlopeTrick {
  using ll = long long;
  struct P {
    ll x, c;
    P(ll _x, ll _c) : x(_x), c(_c) {}
    friend bool operator<(const P& a, const P& b) { return a.x < b.x; }
    friend bool operator>(const P& a, const P& b) { return a.x > b.x; }
  };
  ll addL, addR, min_y;
  priority_queue<P> L;
  priority_queue<P, vector<P>, greater<>> R;
  void pushL(ll x, ll c = 1) { L.emplace(x - addL, c); }
  void pushR(ll x, ll c = 1) { R.emplace(x - addR, c); }
  P getL() { return P{L.top().x + addL, L.top().c}; }
  P getR() { return P{R.top().x + addR, R.top().c}; }
  void popL() { L.pop(); }
  void popR() { R.pop(); }

  SlopeTrick() : addL(0), addR(0), min_y(0) {}

  void debug() {
    cerr << "addL, addR, min_y : ";
    cerr << addL << ", " << addR << ", " << min_y << endl;

    auto LL{L};
    cerr << "L : ";
    while (!LL.empty()) {
      cerr << "( " << LL.top().x + addL << ", " << LL.top().c << " ), ";
      LL.pop();
    }
    cerr << endl;

    auto RR{R};
    cerr << "R : ";
    while (!RR.empty()) {
      cerr << "( " << RR.top().x + addR << ", " << RR.top().c << " ), ";
      RR.pop();
    }
    cerr << endl;

    cerr << "min : ";
    cerr << "( " << get_min().first << ", " << get_min().second << " )" << endl;
  }

  pair<ll, ll> get_min() {
    ll x = L.empty() ? R.empty() ? 0 : getR().x : getL().x;
    return {x, min_y};
  }

  void shift_L(ll a) { addL += a; }
  void shift_R(ll a) { addR += a; }
  void shift_x(ll a) { addL += a, addR += a; }
  void shift_y(ll a) { min_y += a; }

  void add_xma(ll a, ll c = 1) {
    ll used = 0;
    while (used < c && !L.empty()) {
      auto [X, C] = getL();
      if (X <= a) break;
      popL();
      ll tmp = min(c - used, C);
      pushR(X, tmp);
      if (C != tmp) pushL(X, C - tmp);
      min_y += (X - a) * tmp;
      used += tmp;
    }
    if (used) pushL(a, used);
    if (c - used) pushR(a, c - used);
  }

  void add_amx(ll a, ll c = 1) {
    ll used = 0;
    while (used < c && !R.empty()) {
      auto [X, C] = getR();
      if (X >= a) break;
      popR();
      ll tmp = min(c - used, C);
      pushL(X, tmp);
      if (C != tmp) pushR(X, C - tmp);
      min_y += (a - X) * tmp;
      used += tmp;
    }
    if (used) pushR(a, used);
    if (c - used) pushL(a, c - used);
  }

  void add_abs_xma(ll a, ll c = 1) { add_xma(a, c), add_amx(a, c); }

  void chmin_right() { decltype(R){}.swap(R); }
  void chmin_left() { decltype(L){}.swap(L); }

  void merge(SlopeTrick& r) {
    if (L.size() + R.size() < r.L.size() + r.R.size()) swap(*this, r);
    while (!r.L.empty()) {
      auto [x, c] = r.getL();
      r.popL();
      add_amx(x, c);
    }
    while (!r.R.empty()) {
      auto [x, c] = r.getR();
      r.popR();
      add_xma(x, c);
    }
    shift_y(r.min_y);
  }

  ll eval(ll x) {
    ll y = min_y;
    auto LL{L};
    while (!LL.empty()) {
      auto [X, C] = LL.top();
      X += addL;
      if (X < x) break;
      y += (X - x) * C;
      LL.pop();
    }
    auto RR{R};
    while (!RR.empty()) {
      auto [X, C] = RR.top();
      X += addR;
      if (x < X) break;
      y += (x - X) * C;
      RR.pop();
    }
    return y;
  }
};

#endif  // __INCLUDE_LEVEL__