29619번 - 나무나무나 심어야지

근성은 나무에 관심이 많다.

비록 지금은 개발을 하고 있지만, 그렇다고 나무에 대한 애정이 식은 것은 아니다. 어느 날 이진 트리를 가지고 놀던 근성은 이진 트리는 나무임에도 열매가 안 열린다는 사실을 깨닫고 큰 충격에 빠졌다. 근성은 나무는 열매가 반드시 열려야 한다 생각하는 나무 열매..(중략) 론을 밀고 있었기에 나무 열매가 열리는 트리 그래프를 만들었고 이에 "나무나무"라 이름 지었다.

나무나무의 특징은 다음과 같다.

1. 이 트리의 $1$번 정점은 뿌리를 의미한다. 이 트리는 뿌리로부터 위로 뻗어 나간다.
2. $1$번 정점을 제외한 정점은 가지가 갈라지거나 끝나는 지점을 의미한다. 정점에는 가지가 연결될 수 있다. 단, 다른 정점에서 갈라진 가지가 정점에서 합쳐지지는 않는다.
3. 간선은 가지를 의미한다. 가지 양 끝에는 반드시 정점이 존재한다.
4. 정점에는 최대 1개의 열매가 열릴 수 있다. 뿌리에는 열매가 열리지 않는다. 매 쿼리에 앞서 열매가 열릴 수 있는 정점에는 열매가 열린다.

트리를 만든 후 무엇을 할 수 있을까 고민하던 중 아래와 같은 두 가지를 생각해 냈다!

• 1 i j w: (접목) 임의의 정점 $i$에 가지를 붙인다.
  • 정점 $i$는 뿌리와 같은 그래프에 속하는 정점이다.
  • 가지 끝에는 정점이 항상 존재하기에 $j$번으로 번호를 붙인 정점이 새로 생긴 가지 반대쪽에 같이 붙는다.
  • 정점  $j$에는 $w$ 무게의 열매가 달린다. $w=0$은 열매가 열리지 않는다는 뜻이다.
  • ($1 \le i, j \le N + M;$ $0 \le w \le 500$)
• 2 i: (수확) 정점 $i$와, 그 위로 연결된 모든 정점의 열매를 떨어트리려면 몇의 힘으로 흔들어야 할지 출력한다.
  • 임의의 정점 $i$를 흔들면 해당 정점 위로 연결된 가지, 정점들이 모두 같은 힘으로 흔들린다.
  • 정점 $i$를 흔들어 모든 열매를 떨어뜨리기 위해서는 힘이 정점 $i$와 그 위로 연결된 모든 정점에 달린 열매 무게의 합이 되어야 한다.
  • $0$의 힘으로 흔들 수는 없기에 만약, 무게 합이 $0$이라면 -1 을 출력한다.
  • ($1 \le i \le N + M$)

쿼리에 주어지는 수는 모두 정수이고, 올바른 입력임을 보장한다. 또한 수확 쿼리는 1회 이상 주어진다.

그런데 근성은 이 쿼리를 만들다 갑자기 동아리방에 가야 한다며 떠났다. 여러분이 대신 풀어주자.

첫째 줄에 최초 정점의 수 $N$, 쿼리의 수 $M$이 공백으로 구분되어 주어진다. 최초의 정점에는 $1$ 이상 $N$ 이하의 번호가 중복되지 않게 붙어있다. ($2 \le N, M \le 100\,000$)

둘째 줄에 $1$번부터 $N$번까지, 각 정점이 어느 정점의 바로 위에 가지로 연결되어 있는지 공백으로 구분되어 주어진다. $1$번은 뿌리이므로 -1 이 주어진다. 모든 정점은 최종적으로 뿌리와 같은 그래프에 속하지만, 입력 도중에는 속하지 않을 수 있다.

셋째 줄에 $1$번부터 $N$번까지, 각 정점이 가지고 있는 열매의 무게 $w_i$ 가 공백으로 구분되어 주어진다. ($0 \le w_i \le 500$) $0$이라면 열매가 열리지 않는 것이고 뿌리에는 열매가 열리지 않는다.

이후 넷째 줄부터 $M$개의 줄에 걸쳐 쿼리가 주어진다.

수확 쿼리가 들어올 때 몇의 힘으로 흔들어야 할지 출력한다. 단, 흔들어야 할 힘이 $0$이라면 -1 을 출력한다.

1번 예제 테스트 케이스를 확인해보자.

최초 트리의 형태이다. 첫 번째 쿼리 시 $1$번 정점을 흔들면 $2$, $3$번 정점이 같이 흔들리고 $3$번 정점에 달린 열매를 떨어트리기 위해 $3$의 힘으로 흔들어야 한다.

3개 접목을 진행한 모습이다. $4$번 정점을 흔들면 $4$번만 흔들리고, $4$번에 달린 열매를 떨어트리기 위해 $5$의 힘으로 흔들어야 한다. 마찬가지로 $7$번 정점을 흔들면 $7$, $4$, $5$번이 흔들리고 $4$번과 $7$번의 열매를 떨어트리기 위해 $9$의 힘으로 흔들어야 한다.

2번 예제를 확인해보자.

첫 번째 쿼리 시 $1$번 정점을 흔들면 $2$, $3$, $4$번이 같이 흔들리지만, 열매가 달려 있지 않다. 흔들어야 할 힘이 $0$이기에 -1을 출력한다.

$1$번 정점을 흔들면 $2$, $3$, $4$, $7$번이 같이 흔들리고, $7$번의 열매를 떨어트리기 위해 $500$의 힘으로 흔들어야 한다.