1001. Grand Mex
cpp
#pragma GCC optimize("O2")
#include <bits/stdc++.h>
#include <numeric>
using namespace std;
#define int long long
#define i64 int64_t
#define db long double
#define pii pair<int, int>
#define tiii tuple<int, int, int>
#define ull unsigned long long
#define vi vector<int>
using i128 = __int128;
#define vpii vector<pii>
#define vvpii vector<vector<pii>>
#define vvi vector<vi>
#define pqpii priority_queue<pii, vector<pii>, greater<pii>>
#define pqi priority_queue<int, vi, greater<int>>
#define f first
#define s second
#define all(x) (x).begin(), (x).end()
#define pb push_back
#define eb emplace_back
#define sz(x) (x).size()
#define mp make_pair
#define endl '\n'
const int mod = 998244353;
const int INF = 1e18;
const int N = 5e5 + 5;
void init() {}
struct Tarjan {
vector<vector<int>> graph;
vector<int> dfn, low, scc, stk;
vector<bool> instk;
int n, cnt = 0, scc_cnt = 0;
Tarjan(int n) : n(n) {
graph.resize(n + 1);
dfn.resize(n + 1);
low.resize(n + 1);
scc.resize(n + 1);
instk.resize(n + 1);
}
void add_edge(int u, int v) {
graph[u].push_back(v);
}
void dfs(int u) {
dfn[u] = low[u] = ++cnt;
stk.push_back(u);
instk[u] = true;
for (int v : graph[u]) {
if (!dfn[v]) {
dfs(v);
low[u] = min(low[u], low[v]);
} else if (instk[v]) {
low[u] = min(low[u], dfn[v]);
}
}
if (dfn[u] == low[u]) {
scc_cnt++;
while (true) {
int v = stk.back();
stk.pop_back();
instk[v] = false;
scc[v] = scc_cnt;
if (v == u) {
break;
}
}
}
}
void work() {
for (int i = 1; i <= n; i++) {
if (dfn[i]) {
continue;
}
dfs(i);
}
}
};
void solve2(vector<pair<int, int>> &a) {
int n = a.size() + 1;
vector<int> dep(n + 1);
vector<vector<int>> adj(n + 1);
for (auto &[x, y] : a) adj[x].emplace_back(y), adj[y].emplace_back(x);
auto dfs = [&](auto &&self, int x, int fa) -> void {
for (int &y : adj[x]) {
if (y == fa) continue;
dep[y] = dep[x] + 1;
self(self, y, x);
}
};
dfs(dfs, 1, 0);
cout << "2\n";
for (auto &[x, y] : a) {
cout << (dep[x] > dep[y] ? x : y) << ' ';
}
cout << '\n';
}
void solve() {
int n;
cin >> n;
vvpii a(n + 1);
vpii v;
for (int i = 1; i <n; i++) {
int x, y;
cin >> x >> y;
v.pb({x, y});
a[x].pb({i, 0});
a[y].pb({i, 1});
}
Tarjan tj((n - 1) * 2);
auto get = [&](int x, int op, bool to) -> int {
return x+(op^to)*(n-1);
};
for (int i = 1; i <= n; i++) {
if (sz(a[i]) == 1) {
auto [x, op] = a[i][0];
tj.add_edge(get(x, op, 0), get(x, op, 1));
}else{
auto [x1, op1]=a[i].back();
a[i].pop_back();
auto [x2, op2]=a[i].back();
tj.add_edge(get(x1, op1, 0), get(x2, op2, 0));
tj.add_edge(get(x2, op2, 1), get(x1, op1, 1));
tj.add_edge(get(x1, op1, 1), get(x2, op2, 1));
}
}
tj.work();
for(int i=1;i<=n-1;i++){
if(tj.scc[get(i,0,0)]==tj.scc[get(i,0,1)]){
solve2(v);
return;
}
}
cout<<1<<endl;
vi ans;
for(int i=1;i<n;i++){
if(tj.scc[get(i,0,0)]<tj.scc[get(i,0,1)]){
ans.pb(v[i-1].f);
}else{
ans.pb(v[i-1].s);
}
}
for(auto x:ans)cout<<x<<" ";
cout<<endl;
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
init();
int t = 1;
cin >> t;
while (t--) solve();
return 0;
}1002. Dice Tower
cpp
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 1010, M = 1010;
int a[N][N];
LL cnt[1 << 6]; // +i +j -i -j d u 0 -> 5
int mx[1 << 6];
int calc(int msk, const vector<int> &t, int tp) {
int res = 0;
if (msk >> 5 & 1) res += tp;
if (msk >> 4 & 1) res += 7 - tp;
int tmp = 0;
for (int i = 0; i < 4; ++i) {
int cur = 0;
for (int j = 0; j < 4; ++j) {
if (msk >> j & 1) cur += t[(i + j) % 4];
}
tmp = max(tmp, cur);
}
return res + tmp;
}
void init() {
for (int msk = 0; msk < (1 << 6); ++msk) {
mx[msk] = max(mx[msk], calc(msk, {2, 4, 5, 3}, 1));
mx[msk] = max(mx[msk], calc(msk, {6, 4, 1, 3}, 2));
mx[msk] = max(mx[msk], calc(msk, {6, 2, 1, 5}, 3));
mx[msk] = max(mx[msk], calc(msk, {6, 5, 1, 2}, 4));
mx[msk] = max(mx[msk], calc(msk, {1, 4, 6, 3}, 5));
mx[msk] = max(mx[msk], calc(msk, {5, 4, 2, 3}, 6));
}
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
init();
int T;
cin >> T;
while (T--) {
fill(cnt, cnt + (1 << 6), 0);
int n, m;
cin >> n >> m;
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= m; ++j) {
cin >> a[i][j];
}
a[i][0] = a[i][m + 1] = 0;
}
for (int i = 1; i <= m; ++i) a[0][i] = a[n + 1][i] = 0;
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= m; ++j) {
if (a[i][j]){
vector<int> t = {1, a[i + 1][j] + 1, a[i - 1][j] + 1, a[i][j + 1] + 1, a[i][j - 1] + 1};
sort(t.begin(), t.end(), greater<LL>());
t.erase(unique(t.begin(), t.end()), t.end());
int pre = a[i][j];
vector<pair<int, int>> tt;
for (int &k : t) {
int msk = 0;
if (k > a[i + 1][j]) msk |= 1 << 0;
if (k > a[i][j + 1]) msk |= 1 << 1;
if (k > a[i - 1][j]) msk |= 1 << 2;
if (k > a[i][j - 1]) msk |= 1 << 3;
if (pre >= k) tt.emplace_back(msk, pre - k + 1);
pre = min(pre, k - 1);
}
if (tt.size() == 1 && tt.back().second == 1) {
cnt[tt.back().first | 1 << 5 | 1 << 4]++;
}
else {
cnt[tt.front().first | 1 << 5]++;
cnt[tt.back().first | 1 << 4]++;
tt.front().second--, tt.back().second--;
for (auto &[msk, ttt] : tt) cnt[msk] += ttt;
}
}
}
}
LL res = 0;
for (int i = 0; i < (1 << 6); ++i) {
res += cnt[i] * mx[i];
}
cout << res << '\n';
}
return 0;
}1003. Phi Master
cpp
#pragma GCC optimize(2)
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 1e7;
#define debug(x) cout << #x << '=' << x << ' ';
#define DL cout << '\n';
bitset<N + 5> vis;
vector<int> primes;
int phi[N + 5];
ll f[N + 5];
void get_phi(int n) {
phi[1] = 1;
for (int i = 2; i <= n; ++ i) {
if (!vis[i]) {
primes.push_back(i);
phi[i] = i - 1;
}
for (int p:primes) {
if (p * i > n) break;
int m = p * i;
vis[m] = 1;
if (i % p == 0) {
phi[m] = p * phi[i];
break;
} else {
phi[m] = (p - 1) * phi[i];
}
}
}
}
void solve() {
int n;
cin >> n;
memset(f, 0, sizeof f);
for (int i = 0; i < n; i ++) {
int x;
cin >> x;
f[x] = phi[x];
}
vector<ll> ans(1000);
for (int p : primes) for (int i = N / p; i >= 1; i --) f[i] = max(f[i], f[i * p]);
for (int d = 1; d <= N; d ++) if (f[d]) f[d] = f[d] * d / phi[d];
for (int p : primes) for (int i = 1; i <= N / p; i ++) f[i * p] = max(f[i * p], f[i]);
for (int x = 1; x <= N; x ++) ans[x % 1000] ^= (x + 999) / 1000 * (phi[x] * f[x]);
for (int i = 0; i < 1000; ++ i) cout << ans[i] << '\n';
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
//freopen("in.txt", "r", stdin);
//freopen("out.txt", "w", stdout);
get_phi(N);
int t;
cin >> t;
while (t --) solve();
}1004. Three Colors
cpp
int main(){}1006. Gcd Master
cpp
#pragma GCC optimize("O2")
#include <bits/stdc++.h>
#include <numeric>
using namespace std;
#define int long long
#define i64 int64_t
#define db long double
#define pii pair<int, int>
#define tiii tuple<int, int, int>
#define ull unsigned long long
#define vi vector<int>
using i128 = __int128;
#define vpii vector<pii>
#define vvpii vector<vector<pii>>
#define vvi vector<vi>
#define pqpii priority_queue<pii, vector<pii>, greater<pii>>
#define pqi priority_queue<int, vi, greater<int>>
#define f first
#define s second
#define all(x) (x).begin(), (x).end()
#define pb push_back
#define eb emplace_back
#define sz(x) (x).size()
#define mp make_pair
#define endl '\n'
const int mod = 998244353;
const int INF = 1e18;
const int N = 5e5 + 5;
vi a[N];
vvi b;
namespace NTT {
using u32 = uint32_t;
using u64 = uint64_t;
using Poly = vector<u32>;
constexpr u32 mod = 998244353;
constexpr u32 G = 3;
inline u32 add(u32 a, u32 b) {
u32 s = a + b;
return s >= mod ? s - mod : s;
}
inline u32 sub(u32 a, u32 b) {
return a >= b ? a - b : a + mod - b;
}
inline u32 mul(u32 a, u32 b) {
return (u64)a * b % mod;
}
u32 qpow(u32 a, u32 b) {
u32 res = 1;
while (b) {
if (b & 1)
res = mul(res, a);
a = mul(a, a);
b >>= 1;
}
return res;
}
struct FFTInfo {
u32 root[24]{};
u32 iroot[24]{};
u32 rate2[22]{};
u32 irate2[22]{};
u32 rate3[21]{};
u32 irate3[21]{};
FFTInfo() {
root[23] = qpow(G, (mod - 1) >> 23);
iroot[23] = qpow(root[23], mod - 2);
for (int32_t i = 22; i >= 0; i--) {
root[i] = mul(root[i + 1], root[i + 1]);
iroot[i] = mul(iroot[i + 1], iroot[i + 1]);
}
u32 prod = 1;
u32 iprod = 1;
for (int32_t i = 0; i <= 21; i++) {
rate2[i] = mul(root[i + 2], prod);
irate2[i] = mul(iroot[i + 2], iprod);
prod = mul(prod, iroot[i + 2]);
iprod = mul(iprod, root[i + 2]);
}
prod = iprod = 1;
for (int32_t i = 0; i <= 20; i++) {
rate3[i] = mul(root[i + 3], prod);
irate3[i] = mul(iroot[i + 3], iprod);
prod = mul(prod, iroot[i + 3]);
iprod = mul(iprod, root[i + 3]);
}
}
};
const FFTInfo &info() {
static const FFTInfo f;
return f;
}
void ntt(Poly &a) {
int32_t n = (int32_t)a.size();
int32_t h = __builtin_ctz((u32)n);
const auto &f = info();
int32_t len = 0;
while (len < h) {
if (h - len == 1) {
int32_t p = 1 << (h - len - 1);
u32 rot = 1;
for (int32_t s = 0; s < (1 << len); s++) {
int32_t offset = s << (h - len);
for (int32_t i = 0; i < p; i++) {
u32 l = a[offset + i];
u32 r = mul(a[offset + i + p], rot);
a[offset + i] = add(l, r);
a[offset + i + p] = sub(l, r);
}
if (s + 1 != (1 << len)) {
int32_t bit = __builtin_ctz(~(u32)s);
rot = mul(rot, f.rate2[bit]);
}
}
len++;
} else {
int32_t p = 1 << (h - len - 2);
u32 rot = 1;
u32 imag = f.root[2];
for (int32_t s = 0; s < (1 << len); s++) {
u32 rot2 = mul(rot, rot);
u32 rot3 = mul(rot2, rot);
int32_t offset = s << (h - len);
for (int32_t i = 0; i < p; i++) {
u32 a0 = a[offset + i];
u32 a1 = mul(a[offset + i + p], rot);
u32 a2 = mul(a[offset + i + 2 * p], rot2);
u32 a3 = mul(a[offset + i + 3 * p], rot3);
u32 x0 = add(a0, a2);
u32 x1 = sub(a0, a2);
u32 x2 = add(a1, a3);
u32 x3 = mul(sub(a1, a3), imag);
a[offset + i] = add(x0, x2);
a[offset + i + p] = sub(x0, x2);
a[offset + i + 2 * p] = add(x1, x3);
a[offset + i + 3 * p] = sub(x1, x3);
}
if (s + 1 != (1 << len)) {
int32_t bit = __builtin_ctz(~(u32)s);
rot = mul(rot, f.rate3[bit]);
}
}
len += 2;
}
}
}
void intt(Poly &a) {
int32_t n = (int32_t)a.size();
int32_t h = __builtin_ctz((u32)n);
const auto &f = info();
int32_t len = h;
while (len) {
if (len == 1) {
int32_t p = 1 << (h - len);
u32 irot = 1;
for (int32_t s = 0; s < (1 << (len - 1)); s++) {
int32_t offset = s << (h - len + 1);
for (int32_t i = 0; i < p; i++) {
u32 l = a[offset + i];
u32 r = a[offset + i + p];
a[offset + i] = add(l, r);
a[offset + i + p] = mul(sub(l, r), irot);
}
if (s + 1 != (1 << (len - 1))) {
int32_t bit = __builtin_ctz(~(u32)s);
irot = mul(irot, f.irate2[bit]);
}
}
len--;
} else {
int32_t p = 1 << (h - len);
u32 irot = 1;
u32 iimag = f.iroot[2];
for (int32_t s = 0; s < (1 << (len - 2)); s++) {
u32 irot2 = mul(irot, irot);
u32 irot3 = mul(irot2, irot);
int32_t offset = s << (h - len + 2);
for (int32_t i = 0; i < p; i++) {
u32 a0 = a[offset + i];
u32 a1 = a[offset + i + p];
u32 a2 = a[offset + i + 2 * p];
u32 a3 = a[offset + i + 3 * p];
u32 x0 = add(a0, a1);
u32 x1 = sub(a0, a1);
u32 x2 = add(a2, a3);
u32 x3 = mul(sub(a2, a3), iimag);
a[offset + i] = add(x0, x2);
a[offset + i + p] =
mul(add(x1, x3), irot);
a[offset + i + 2 * p] =
mul(sub(x0, x2), irot2);
a[offset + i + 3 * p] =
mul(sub(x1, x3), irot3);
}
if (s + 1 != (1 << (len - 2))) {
int32_t bit = __builtin_ctz(~(u32)s);
irot = mul(irot, f.irate3[bit]);
}
}
len -= 2;
}
}
}
Poly naive(const Poly &a, const Poly &b) {
int32_t n = (int32_t)a.size();
int32_t m = (int32_t)b.size();
Poly c(n + m - 1);
if (n < m) {
for (int32_t i = 0; i < n; i++) {
for (int32_t j = 0; j < m; j++) {
c[i + j] =
(c[i + j] + (u64)a[i] * b[j]) % mod;
}
}
} else {
for (int32_t j = 0; j < m; j++) {
for (int32_t i = 0; i < n; i++) {
c[i + j] =
(c[i + j] + (u64)a[i] * b[j]) % mod;
}
}
}
return c;
}
Poly convolution(Poly a, Poly b) {
if (a.empty() || b.empty())
return {};
int32_t n = (int32_t)a.size();
int32_t m = (int32_t)b.size();
if (min(n, m) <= 60) {
return naive(a, b);
}
int32_t need = n + m - 1;
int32_t len = 1;
while (len < need) len <<= 1;
assert(len <= (1 << 23));
a.resize(len);
b.resize(len);
ntt(a);
ntt(b);
for (int32_t i = 0; i < len; i++) {
a[i] = mul(a[i], b[i]);
}
intt(a);
u32 inv_len = qpow((u32)len, mod - 2);
a.resize(need);
for (u32 &x : a) {
x = mul(x, inv_len);
}
return a;
}
vector<long long> multiply(
const vector<long long> &A,
const vector<long long> &B) {
Poly a(A.size());
Poly b(B.size());
for (size_t i = 0; i < A.size(); i++) {
long long x = A[i] % (long long)mod;
if (x < 0)
x += mod;
a[i] = (u32)x;
}
for (size_t i = 0; i < B.size(); i++) {
long long x = B[i] % (long long)mod;
if (x < 0)
x += mod;
b[i] = (u32)x;
}
Poly c = convolution(move(a), move(b));
return vector<long long>(c.begin(), c.end());
}
} // namespace NTT
struct Comb {
int n;
long long mod;
vector<long long> fac, invfac;
Comb(int _n, long long _mod) {
n = _n;
mod = _mod;
fac.assign(n + 1, 1);
invfac.assign(n + 1, 1);
for (int i = 1; i <= n; i++) {
fac[i] = fac[i - 1] * i % mod;
}
invfac[n] = qpow(fac[n], mod - 2);
for (int i = n - 1; i >= 0; i--) {
invfac[i] = invfac[i + 1] * (i + 1) % mod;
}
}
long long qpow(long long a, long long b) {
long long res = 1;
while (b) {
if (b & 1)
res = res * a % mod;
a = a * a % mod;
b >>= 1;
}
return res;
}
long long A(int n, int m) {
if (m < 0 || m > n)
return 0;
return fac[n] * invfac[n - m] % mod;
}
long long C(int n, int m) {
if (m < 0 || m > n)
return 0;
return fac[n] * invfac[m] % mod * invfac[n - m] % mod;
}
};
void init() {
for (int i = 1; i < N; i++) {
for (int j = i; j < N; j += i) a[j].pb(i);
sort(all(a[i]));
}
}
Comb C(N, mod);
int get(int t) {
int res = 0;
vi d;
for (auto i : a[t]) d.pb(t / i);
for (int i = sz(d) - 1; i >= 0; i--) {
for (int j = i + 1; j < sz(d); j++)
if (a[t][j] % a[t][i]==0)
d[i] -= d[j];
}
for (int i = 0; i < sz(d); i++) res += d[i] * a[t][i] % mod;
return res % mod;
}
void solve() {
int n;
cin >> n;
b.resize(n + 1);
for (int i = 1; i <= n; i++) {
vi aa, bb;
int m = n / i;
for (int j = 0; j <= n; j += i) {
aa.pb(C.fac[(m - j / i) * i]);
bb.pb(C.invfac[j]);
}
vi c = NTT::multiply(aa, bb);
b[i] = c;
}
auto get2 = [&](int t) -> int {
int res = 0;
vi d;
for (auto i : a[t]) d.pb(b[i][n/i-t/i]*C.invfac[t]%mod);
for (int i = sz(d) - 1; i >= 0; i--) {
for (int j = i + 1; j < sz(d); j++)
if (a[t][j] % a[t][i]==0)
d[i] -= d[j];
}
for (int i = 0; i < sz(d); i++) res += d[i] * a[t][i] % mod;
return res % mod;
};
int ans = 0;
for(int i = 1; i <= n; i++){
ans += get2(i)*get(i)%mod;
ans %= mod;
}
cout << ans << "\n";
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
init();
int t = 1;
cin >> t;
while (t--) solve();
return 0;
}1008. CuteSafari
cpp
#include <bits/stdc++.h>
using namespace std;
bool solve() {
int n, k;
string a, b;
int c1[26]{}, c2[26]{};
cin >> n >> k >> a >> b;
for (int i = 2; i < k; ++i) {
if (a[i - 1] != b[i - 1]) return false;
if (a[n - i] != b[n - i]) return false;
}
for (int i = 0; i < n; ++i) c1[a[i] - 'a'] ++, c2[b[i] - 'a']++;
for (int i = 0; i < 26; ++i) {
if (c1[i] != c2[i]) {
return false;
}
}
if (n < k * 2) {
if (a == b) return true;
swap(a.front(), a.back());
if (a == b) return true;
return false;
}
if (n == k * 2) {
vector<char> t1 = {a[0], a[k - 1], a[k], a[n - 1]}, t2 = {b[0], b[k - 1], b[k], b[n - 1]};
set<long long> vis;
queue<vector<char>> q;
auto get = [](vector<char> a) -> long long {
long long res = 0;
return ((long long)a[0] + a[1] * 131LL + a[2] * 131LL * 131LL + a[3] * 131LL * 131LL * 131LL);
};
q.emplace(t1);
vis.insert(get(t1));
while (!q.empty()) {
auto x = q.front();
q.pop();
if (x == t2) {
return true;
}
swap(x.front(), x.back());
long long h = get(x);
if (!vis.count(h)) vis.emplace(h), q.emplace(x);
swap(x.front(), x.back());
swap(x[0], x[1]), swap(x[2], x[3]);
h = get(x);
if (!vis.count(h)) vis.emplace(h), q.emplace(x);
}
return false;
}
return true;
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
int T;
cin >> T;
while (T--) {
if (solve()) cout << "Yes\n";
else cout << "No\n";
}
return 0;
}1009. Imperfect Permutation
cpp
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
void solve() {
int n;
cin >> n;
vector<pair<ll, int>> a;
int N = 1 << n;
for (int i = 0; i < N; i ++) {
ll pos = 0;
int p;
cin >> p;
for (int b = 0; b < n; b ++) {
int x = i >> b & 1;
int y = p >> b & 1;
int q = x << 1 | y;
pos |= 1LL * q << (2 * b);
}
a.push_back({pos, 1});
}
sort(a.begin(), a.end());
for (int _ = 1; _ <= n; _ ++) {
vector<pair<ll, int>> b;
int cur = 0;
for (; cur < size(a); cur ++) {
int v[4] = {0};
auto [pos, val] = a[cur];
ll fa = pos >> 2;
int kind = pos & 0b11;
v[kind] += val;
while (cur + 1 < size(a) && ((a[cur + 1].first) >> 2) == fa) {
cur ++;
v[a[cur].first & 0b11] += a[cur].second;
}
b.push_back({fa, max(v[0] + v[3], v[1] + v[2])});
}
a.swap(b);
}
cout << a[0].second << '\n';
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
int t;
cin >> t;
while (t --) solve();
}1010. Card Damage
cpp
#pragma GCC optimize("O2")
#include <bits/stdc++.h>
#include <numeric>
using namespace std;
#define int long long
#define i64 int64_t
#define db long double
#define pii pair<int, int>
#define tiii tuple<int, int, int>
#define ull unsigned long long
#define vi vector<int>
using i128 = __int128;
#define vpii vector<pii>
#define vvpii vector<vector<pii>>
#define vvi vector<vi>
#define pqpii priority_queue<pii, vector<pii>, greater<pii>>
#define pqi priority_queue<int, vi, greater<int>>
#define f first
#define s second
#define all(x) (x).begin(), (x).end()
#define pb push_back
#define eb emplace_back
#define sz(x) (x).size()
#define mp make_pair
#define endl '\n'
const int mod = 998244353;
const int INF = 1e18;
const int N = 1e6 + 5;
void init() {}
void solve() {
int x, y;
cin >> x >> y;
int n = x + y;
int m = y + 1;
int q = n / m;
int r = n % m;
int sum = (m - r) * q * q + r * (q + 1) * (q + 1);
int ans = (n * n - sum) / 2;
cout << ans << endl;
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
init();
int t = 1;
cin >> t;
while (t--) solve();
return 0;
}1012. P2P
cpp
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
void disablesync()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
}
#define endl '\n'
const int N=2e5+5;
ll a[N],s[N];
vector<int> edge[N];
void dfs(int u)
{
for (int v:edge[u])
{
if (v<u)
{
s[v]=s[u];
dfs(v);
}
else
{
s[v]=s[u]+1;
dfs(v);
}
}
}
void SOLVE()
{
int n;
cin>>n;
for (int i=1;i<=n;i++) edge[i].clear();
for (int i=1;i<=n;i++) cin>>a[i];
for (int v=2,u;v<=n;v++)
{
cin>>u;
edge[u].push_back(v);
}
s[1]=-1;
dfs(1);
//for (int i=1;i<=n;i++) cout<<s[i]<<" ";cout<<endl;
ll sum=0;
for (int i=2;i<=n;i++) sum+=a[i];
if (sum>0)
{
cout<<1<<endl;
return ;
}
if (sum<0)
{
cout<<-1<<endl;
return ;
}
sum=0;
for (int i=2;i<=n;i++) sum+=s[i]*a[i];
if (sum>0) cout<<-1<<endl;
else if (sum<0) cout<<1<<endl;
else cout<<0<<endl;
}
int main()
{
disablesync();
int t;
cin>>t;
while (t--) SOLVE();
return 0;
}