32251번 - 나무 물 주기

문제

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

나무는 $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)$째 줄에는 각 정점의 열매의 크기를 의미하는 $N$개의 양의 정수 $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$보다 작거나 같은 가장 큰 정수를 의미한다.