문제

개의 정점으로 이루어진 트리가 있다. 각 정점에는 번부터 번까지 번호가 매겨져 있으며, 번 () 정점의 초기 값은 이다.

트리에서 다음의 쿼리 개를 수행하는 프로그램을 작성하시오. 번째 () 쿼리는 다음 가지 중 하나이다.

• 번 쿼리: 번 정점의 값 에 를 더한다.
• 번 쿼리: 번 정점과 거리가 이하인 모든 정점의 값의 합을 출력한다.

두 정점 , () 사이의 거리는 두 정점을 잇는 최단 경로에 포함된 간선의 개수를 의미한다.

입력

첫째 줄에 과 가 공백으로 구분되어 주어진다.

둘째 줄에 이 공백으로 구분되어 주어진다.

다음 개의 줄의 번째 () 줄에는 번째 간선이 연결하는 두 정점의 번호 , 가 공백으로 구분되어 주어진다.

다음 개의 줄의 번째 () 줄에는 번째 쿼리가 주어진다. 쿼리는 다음 형식으로 주어진다.

• 번 쿼리:
• 번 쿼리:

출력

번 쿼리가 주어질 때마다 정답을 한 줄에 하나씩 출력한다.

제약 조건

• ()
• ()
• ()
• ()
• 주어지는 그래프는 트리 구조이다.
• 번 쿼리는 번 이상 주어진다.
• 입력으로 주어지는 모든 수는 정수이다.