나무 물 주기

목이 마른 나무에게 물을 주자.

나무는 $N$개의 정점과 $(N-1)$개의 간선으로 이루어져 있으며, 어느 두 정점 사이에도 단순 경로가 유일하게 존재하는 그래프이다. $1$번 정점을 나무의 뿌리라고 한다. $i$번 정점과 간선으로 직접 연결되어 있으면서 뿌리와의 단순 경로 길이가 $i$번 정점보다 더 큰 정점을 $i$번 정점의 자식 정점이라고 한다.

각 정점에는 열매가 하나씩 달려 있다. 열매는 자신의 크기만큼 물을 흡수할 수 있으며, 물을 주면 가능한 최대로 흡수한다. 열매는 흡수한 물의 양만큼 커진다.

자식 정점이 하나 이상 있다면, 열매가 흡수하고 남은 물은 간선으로 이어진 자식 정점들에게 나뉘어 흘러간다. 각 자식 정점에게 흘러가는 물의 양은 $\left\lfloor {\frac{\text{남은 물의 양}}{\text{자식 정점의 수}}} \right\rfloor$이다.

나무에 물을 주기 위해 $Q$개의 쿼리를 수행하라.

• 1 u x: 정점 $u$에 $x$만큼의 물을 준다. ($1\le u\le N$; $1\le x\le 10^9$)
• 2 u: 정점 $u$의 열매의 크기를 출력한다. ($1\le u\le N$)

첫째 줄에 정점의 개수 $N$과 쿼리의 개수 $Q$가 공백으로 구분되어 주어진다. ($1\le N\le 100\,000$; $1\le Q\le 100\,000$)

둘째 줄부터 $N-1$개의 줄에 걸쳐 간선을 이루는 두 정점 $u$와 $v$가 공백으로 구분되어 주어진다. ($1\le u,v\le N$; $u\neq v$)

$(N+1)$번째 줄에는 각 정점의 열매 크기를 뜻하는 양의 정수 $x_1$, $x_2$, $\cdots$, $x_N$이 공백으로 구분되어 주어진다. ($1\le x_i\le 10^9$)

$(N+2)$번째 줄부터 $Q$개의 줄에 걸쳐 쿼리가 주어진다. 각 쿼리는 1 u x 또는 2 u이다. ($1\le u\le N$; $1\le x\le 10^9$)

모든 입력은 정수이며, 2번 쿼리는 한 번 이상 주어진다.

2번 쿼리마다 해당 쿼리의 정답을 한 줄에 하나씩 출력한다.

$\lfloor{x}\rfloor$는 $x$보다 작거나 같은 가장 큰 정수를 의미한다.