牛奶

梓想要喝牛奶，但是奶牛在树上。

给定一个有 $N$ 个点，$N-1$ 条边的无向连通图，点 $i$ 有点权 $d_i$，点权可正可负。奶牛初始在 $1$ 号点，需要沿着某条路径（不一定是简单路径，即点和边均可以经过多次）到达 $N$ 号点。

奶牛有一个得分，初始为 $0$，在第一次经过一个点 $i$（包括点 $1$ 和点 $N$）时，奶牛的得分会加上 $d_i$。奶牛需要确保得分始终不小于 $0$，求是否存在满足条件的路径。

输入格式

本题有多组数据。

第一行一个正整数 $T$，表示数据组数。

对于每组数据：

第一行一个正整数 $N$。

接下来一行 $N-1$ 个整数 $u_2,u_3,\dots,u_N$，表示点 $i$ 与点 $u_i$ 之间有一条无向边。保证 $1\le u_i\le i-1$，且最终形成的图是连通图。

最后一行 $N$ 个整数，表示 $d_1,d_2,\dots,d_N$。

输出格式

对于每组数据，输出一行一个整数：

若有解，则输出 1，否则输出 0。

样例

ex_milk1.in
2
7
1 2 2 1 5 6
0 -3 2 2 3 -4 0
3
1 2
3 -4 3
ex_milk1.out
1
0

数据范围

奶牛提醒您：

数据千万条，清空第一条。

多测不清空，爆零两行泪。

对于所有测试点，满足 $T\le 10, N\le 2*10^5, -10^6\le d_i\le 10^6, d_1\ge 0$。

下表中的 $K$ 表示：该测试点至多有两组数据使得 $N>K$，/表示该测试点无此限制。