뉴스

데니는 $N$명의 직원이 있는 회사의 사장이다. 직원은 $1$번부터 $N$번까지 번호가 붙어 있다. 회사의 조직은 엄격한 상하 관계로, $1$번을 제외한 모든 직원은 직속 상사가 정확히 한 명 있다. 따라서 모든 직원은 자기 자신을 포함해 $1$명 이상의 부하 직원(직속 및 간접)을 가진다. 예를 들어 $1$번 직원은 자기 자신을 포함해 정확히 $N$명의 부하 직원을 가진다. 물론 어떤 직원의 부하가 그 직원의 직속 상사인 경우는 없다. 어떤 직원 $x$에 대해 $x$를 $x$의 $0$레벨 부하라고 부르자. 그러면 $x$의 직속 부하는 $x$의 $1$레벨 부하라고 부른다. 그들의 직속 부하($x$의 간접 부하)는 모두 $x$의 $2$레벨 부하라고 부르는 식이다.

어떤 직원 몇 명이 어떤 충격적인 뉴스를 알고 있다. 데니는 회사의 모든 직원에게 이 뉴스를 알리고 싶어 한다. 그래서 여러 번 직원 $x$와 수 $k$를 골라 $x$의 $0$레벨, $1$레벨(존재한다면), …, $k$레벨(존재한다면) 부하 모두에게 뉴스를 알린다. 이 부하들을 모두 $x$의 $k$-부하라고 부르자. 이런 방식으로 알리면 고른 부하 중 이미 뉴스를 아는 사람이 많다는 게 문제다. 그래서 데니는 $x$의 $k$-부하 중 뉴스를 이미 알고 있는 직원의 수를 알려 주는 시스템을 원한다. 데니를 도울 프로그램을 작성하라.

표준 입력의 첫째 줄에서 정수 $N$을 읽는다. $N$은 데니 회사의 직원 수다. 다음 $N-1$개 줄 각각에서 정수 $x$와 $y$를 읽는다. 이는 직원 $y$가 직원 $x$의 직속 부하라는 뜻이다. 그다음 줄에서 정수 $N$개 $b_1, b_2, \ldots, b_N$을 읽는다. $b_i$는 처음에 직원 $i$가 뉴스를 알면 $1$, 모르면 $0$이다. 그다음 줄에서 정수 $Q$를 읽는다. $Q$는 질의의 수다. 마지막 $Q$개 줄 각각에서 두 종류의 질의를 읽는다.

• 종류 $1$(뉴스 알림 질의): $1$ $x$ $k$ – 데니가 $x$의 $k$-부하 모두에게 뉴스를 알린다.
• 종류 $2$(질문 질의): $2$ $x$ $k$ – 데니가 $x$의 $k$-부하 중 뉴스를 아는 직원의 수를 묻는다.

종류 $2$의 질의마다 입력 순서와 같은 순서로 한 줄에 정수 하나씩 답을 출력한다.

• $2 ≤ N ≤ 2 × 10^5$
• $1 ≤ Q ≤ 2 × 10^5$
• $0 ≤ k ≤ N$

위 그림은 회사의 조직과 처음에 뉴스를 아는 직원을 주황색으로 표시한 것이다.

첫 번째 질의 $2$ $4$ $4$에 대해:

직원 $4$의 $0$레벨 부하는 $4$, $1$레벨 부하는 직원 $7$과 $8$, $2$레벨 부하는 $9$와 $10$이고 $3$레벨과 $4$레벨 부하는 없다. 직원 $4$, $8$, $10$이 뉴스를 알고 있으므로 이 질문 질의의 답은 $3$이다.

질의 $1$ $4$ $1$에 대해:

직원 $4$의 $1$-부하는 직원 $4$, $7$, $8$이다. 직원 $4$와 $8$은 이미 뉴스를 알고 있으므로 이때 뉴스를 알게 되는 직원은 $7$뿐이다.

두 번째 질의 $2$ $4$ $4$에 대해:

직원 $4$의 $4$-부하는 $4$, $7$, $8$, $9$, $10$이다. 직원 $4$, $7$, $8$, $10$이 뉴스를 알고 있으므로 이번 질의의 답은 $4$이다.