//============================================================================
// Name : firstTrial.cpp
// Author :
// Version :
// Copyright : Your copyright notice
// Description : Hello World in C++, Ansi-style
//============================================================================
#include <bits/stdc++.h>
using namespace std;
const int N = 5e5 + 20, MOD = 1e9 + 7;;
int seg[4 * N];
vector<int> adj[N];
int club[N], level[N], ans[N], in[N], out[N], T, add[N], rmove[N], addIdx, removeIdx;
pair<int,pair<int, int> > que[N];
void pre(int n){
for(int i = 0; i < n; i++)
que[i].second.first = level[que[i].second.second];
sort(que, que + n);
}
void dfs(int u){
in[u] = T++;
for(int i = 0; i < (int)adj[u].size(); i++)
dfs(adj[u][i]);
out[u] = T - 1;
}
void up(int l, int r, int idx, int qidx, int val){
if(qidx < l || r < qidx)
return;
if(l == r){
seg[idx] = val;
return;
}
int mid = (l + r) / 2;
up(l, mid, idx * 2, qidx, val);
up(mid + 1, r, idx * 2 + 1, qidx, val);
seg[idx] = (0ll + seg[idx * 2] + seg[idx * 2 + 1]) % MOD;
}
int sum(int l, int r, int idx, int ql, int qr){
if(r < ql || qr < l)
return 0;
if(ql <= l && r <= qr)
return seg[idx];
int mid = (l + r) / 2;
return (0ll + sum(l, mid, idx * 2, ql, qr) + sum(mid + 1, r, idx * 2 + 1, ql, qr)) % MOD;
}
void solve(int n){
T = 0;
dfs(0);
assert(T < 500010);
addIdx = removeIdx = -1;
bool flag;
for(int i = 0; i < n; i++){
if(i == 0 || (i && que[i].first != que[i - 1].first)){
while(removeIdx != -1){
int cur = rmove[removeIdx];
up(0, T + 1, 1, in[cur], 0);
removeIdx--;
}
addIdx = -1;
flag = 0;
}
if(flag){
ans[que[i].second.second] = 0;
continue;
}
if((i && que[i].first == que[i - 1].first && (que[i].second.first == que[i - 1].second.first || que[i].second.first - 1 == que[i - 1].second.first))
|| (i && que[i].first != que[i - 1].first && que[i].second.first == 0) || (i == 0 && que[i].second.first == 0)){
if(i && que[i].first == que[i - 1].first && que[i].second.first != que[i - 1].second.first){
while(removeIdx != -1){
int cur = rmove[removeIdx];
up(0, T + 1, 1, in[cur], 0);
removeIdx--;
}
while(addIdx != -1){
int cur = add[addIdx];
up(0, T + 1, 1, in[cur], ans[cur]);
rmove[++removeIdx] = cur;
addIdx--;
}
}
if(que[i].second.first == 0)
ans[que[i].second.second] = 1;
else
ans[que[i].second.second] = sum(0, T + 1, 1, in[que[i].second.second], out[que[i].second.second]);
}else
flag = 1, ans[que[i].second.second] = 0;
add[++addIdx] = que[i].second.second;
}
while(removeIdx != -1){
int cur = rmove[removeIdx];
up(0, T + 1, 1, in[cur], 0);
removeIdx--;
}
}
int main(){
int t;
scanf("%d", &t);
while(t--){
memset(adj, 0, sizeof adj);
int x, n;
scanf("%d%d", &n, &x);
for(int i = 1; i < n; i++){
int z;
scanf("%d", &z);
adj[z].push_back(i);
}
for(int i = 0; i < n; i++){
scanf("%d", &club[i]);
que[i] = make_pair(club[i], make_pair(-1, i));
}
for(int i = 0; i < n; i++)
scanf("%d", &level[i]);
pre(n);
solve(n);
for(int i = 0; i < n; i++){
printf("%d\n", ans[i]);
}
}
return 0;
}
Ly89PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09Ci8vIE5hbWUgOiBmaXJzdFRyaWFsLmNwcAovLyBBdXRob3IgOgovLyBWZXJzaW9uIDoKLy8gQ29weXJpZ2h0IDogWW91ciBjb3B5cmlnaHQgbm90aWNlCi8vIERlc2NyaXB0aW9uIDogSGVsbG8gV29ybGQgaW4gQysrLCBBbnNpLXN0eWxlCi8vPT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PQoKI2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+Cgp1c2luZyBuYW1lc3BhY2Ugc3RkOwpjb25zdCBpbnQgTiA9IDVlNSArIDIwLCBNT0QgPSAxZTkgKyA3OzsKaW50IHNlZ1s0ICogTl07CnZlY3RvcjxpbnQ+IGFkaltOXTsKaW50IGNsdWJbTl0sIGxldmVsW05dLCBhbnNbTl0sIGluW05dLCBvdXRbTl0sIFQsIGFkZFtOXSwgcm1vdmVbTl0sIGFkZElkeCwgcmVtb3ZlSWR4OwpwYWlyPGludCxwYWlyPGludCwgaW50PiA+IHF1ZVtOXTsKdm9pZCBwcmUoaW50IG4pewoJZm9yKGludCBpID0gMDsgaSA8IG47IGkrKykKCQlxdWVbaV0uc2Vjb25kLmZpcnN0ID0gbGV2ZWxbcXVlW2ldLnNlY29uZC5zZWNvbmRdOwoJc29ydChxdWUsIHF1ZSArIG4pOwp9Cgp2b2lkIGRmcyhpbnQgdSl7Cglpblt1XSA9IFQrKzsKCWZvcihpbnQgaSA9IDA7IGkgPCAoaW50KWFkalt1XS5zaXplKCk7IGkrKykKCQlkZnMoYWRqW3VdW2ldKTsKCW91dFt1XSA9IFQgLSAxOwp9CnZvaWQgdXAoaW50IGwsIGludCByLCBpbnQgaWR4LCBpbnQgcWlkeCwgaW50IHZhbCl7CglpZihxaWR4IDwgbCB8fCByIDwgcWlkeCkKCQlyZXR1cm47CglpZihsID09IHIpewoJCXNlZ1tpZHhdID0gdmFsOwoJCXJldHVybjsKCX0KCWludCBtaWQgPSAobCArIHIpIC8gMjsKCXVwKGwsIG1pZCwgaWR4ICogMiwgcWlkeCwgdmFsKTsKCXVwKG1pZCArIDEsIHIsIGlkeCAqIDIgKyAxLCBxaWR4LCB2YWwpOwoJc2VnW2lkeF0gPSAoMGxsICsgc2VnW2lkeCAqIDJdICsgc2VnW2lkeCAqIDIgKyAxXSkgJSBNT0Q7Cn0KaW50IHN1bShpbnQgbCwgaW50IHIsIGludCBpZHgsIGludCBxbCwgaW50IHFyKXsKCWlmKHIgPCBxbCB8fCBxciA8IGwpCgkJcmV0dXJuIDA7CglpZihxbCA8PSBsICYmIHIgPD0gcXIpCgkJcmV0dXJuIHNlZ1tpZHhdOwoJaW50IG1pZCA9IChsICsgcikgLyAyOwoJcmV0dXJuICgwbGwgKyBzdW0obCwgbWlkLCBpZHggKiAyLCBxbCwgcXIpICsgc3VtKG1pZCArIDEsIHIsIGlkeCAqIDIgKyAxLCBxbCwgcXIpKSAlIE1PRDsKfQp2b2lkIHNvbHZlKGludCBuKXsKCVQgPSAwOwoJZGZzKDApOwoJYXNzZXJ0KFQgPCA1MDAwMTApOwoKCWFkZElkeCA9IHJlbW92ZUlkeCA9IC0xOwoJYm9vbCBmbGFnOwoJZm9yKGludCBpID0gMDsgaSA8IG47IGkrKyl7CgkJaWYoaSA9PSAwIHx8IChpICYmIHF1ZVtpXS5maXJzdCAhPSBxdWVbaSAtIDFdLmZpcnN0KSl7CgkJCXdoaWxlKHJlbW92ZUlkeCAhPSAtMSl7CgkJCQlpbnQgY3VyID0gcm1vdmVbcmVtb3ZlSWR4XTsKCQkJCXVwKDAsIFQgKyAxLCAxLCBpbltjdXJdLCAwKTsKCQkJCXJlbW92ZUlkeC0tOwoJCQl9CgkJCWFkZElkeCA9IC0xOwoJCQlmbGFnID0gMDsKCQl9CgkJaWYoZmxhZyl7CgkJCWFuc1txdWVbaV0uc2Vjb25kLnNlY29uZF0gPSAwOwoJCQljb250aW51ZTsKCQl9CgkJaWYoKGkgJiYgcXVlW2ldLmZpcnN0ID09IHF1ZVtpIC0gMV0uZmlyc3QgJiYgKHF1ZVtpXS5zZWNvbmQuZmlyc3QgPT0gcXVlW2kgLSAxXS5zZWNvbmQuZmlyc3QgfHwgcXVlW2ldLnNlY29uZC5maXJzdCAtIDEgPT0gcXVlW2kgLSAxXS5zZWNvbmQuZmlyc3QpKQoJCQkJfHwgKGkgJiYgcXVlW2ldLmZpcnN0ICE9IHF1ZVtpIC0gMV0uZmlyc3QgJiYgcXVlW2ldLnNlY29uZC5maXJzdCA9PSAwKSB8fCAoaSA9PSAwICYmIHF1ZVtpXS5zZWNvbmQuZmlyc3QgPT0gMCkpewoJCQlpZihpICYmIHF1ZVtpXS5maXJzdCA9PSBxdWVbaSAtIDFdLmZpcnN0ICYmIHF1ZVtpXS5zZWNvbmQuZmlyc3QgIT0gcXVlW2kgLSAxXS5zZWNvbmQuZmlyc3QpewoJCQkJd2hpbGUocmVtb3ZlSWR4ICE9IC0xKXsKCQkJCQlpbnQgY3VyID0gcm1vdmVbcmVtb3ZlSWR4XTsKCQkJCQl1cCgwLCBUICsgMSwgMSwgaW5bY3VyXSwgMCk7CgkJCQkJcmVtb3ZlSWR4LS07CgkJCQl9CgkJCQl3aGlsZShhZGRJZHggIT0gLTEpewoJCQkJCWludCBjdXIgPSBhZGRbYWRkSWR4XTsKCQkJCQl1cCgwLCBUICsgMSwgMSwgaW5bY3VyXSwgYW5zW2N1cl0pOwoJCQkJCXJtb3ZlWysrcmVtb3ZlSWR4XSA9IGN1cjsKCQkJCQlhZGRJZHgtLTsKCQkJCX0KCQkJfQoJCQlpZihxdWVbaV0uc2Vjb25kLmZpcnN0ID09IDApCgkJCQlhbnNbcXVlW2ldLnNlY29uZC5zZWNvbmRdID0gMTsKCQkJZWxzZQoJCQkJYW5zW3F1ZVtpXS5zZWNvbmQuc2Vjb25kXSA9IHN1bSgwLCBUICsgMSwgMSwgaW5bcXVlW2ldLnNlY29uZC5zZWNvbmRdLCBvdXRbcXVlW2ldLnNlY29uZC5zZWNvbmRdKTsKCgkJfWVsc2UKCQkJZmxhZyA9IDEsIGFuc1txdWVbaV0uc2Vjb25kLnNlY29uZF0gPSAwOwoJCWFkZFsrK2FkZElkeF0gPSBxdWVbaV0uc2Vjb25kLnNlY29uZDsKCX0KCXdoaWxlKHJlbW92ZUlkeCAhPSAtMSl7CgkJaW50IGN1ciA9IHJtb3ZlW3JlbW92ZUlkeF07CgkJdXAoMCwgVCArIDEsIDEsIGluW2N1cl0sIDApOwoJCXJlbW92ZUlkeC0tOwoJfQp9CgoKaW50IG1haW4oKXsKCWludCB0OwoJc2NhbmYoIiVkIiwgJnQpOwoJd2hpbGUodC0tKXsKCQltZW1zZXQoYWRqLCAwLCBzaXplb2YgYWRqKTsKCQlpbnQgeCwgbjsKCQlzY2FuZigiJWQlZCIsICZuLCAmeCk7CgkJZm9yKGludCBpID0gMTsgaSA8IG47IGkrKyl7CgkJCWludCB6OwoJCQlzY2FuZigiJWQiLCAmeik7CgkJCWFkalt6XS5wdXNoX2JhY2soaSk7CgkJfQoJCWZvcihpbnQgaSA9IDA7IGkgPCBuOyBpKyspewoJCQlzY2FuZigiJWQiLCAmY2x1YltpXSk7CgkJCXF1ZVtpXSA9IG1ha2VfcGFpcihjbHViW2ldLCBtYWtlX3BhaXIoLTEsIGkpKTsKCQl9CgkJZm9yKGludCBpID0gMDsgaSA8IG47IGkrKykKCQkJc2NhbmYoIiVkIiwgJmxldmVsW2ldKTsKCQlwcmUobik7CgkJc29sdmUobik7CgkJZm9yKGludCBpID0gMDsgaSA8IG47IGkrKyl7CgkJCXByaW50ZigiJWRcbiIsIGFuc1tpXSk7CgkJfQoJfQoJcmV0dXJuIDA7Cn0K