Juke Artem

시간 제한2초메모리 제한512 MB

요약

트리의 간선을 따라 두 값을 교환해 모든 수를 제자리에 놓는 최소 비용을 구합니다.

난이도: 보통10점 중 6점
유형: 트리, 그리디, 수학
정답자: 아직 제출이 없습니다

문제

$n$ 개의 정점으로 이루어진 트리가 주어진다. 정점은 $0$ 부터 $n - 1$ 까지 번호가 붙어 있다. 각 정점에는 수가 하나씩 적혀 있으며, 수는 $0$ 부터 $n - 1$ 까지이고 모두 서로 다르다(즉, 순열을 이룬다). 수 $x$ 가 $x$ 번 정점에 있으면 수 $x$ 는 제자리에 있다고 한다.

트리의 간선 하나의 양 끝점에 있는 두 수를 서로 교환할 수 있다. 교환 전에 두 수 중 적어도 하나가 제자리에 있었다면 비용은 0이고, 그렇지 않으면 1이다.

모든 수를 제자리에 놓는 데 드는 최소 비용은 얼마인가?

입력

첫째 줄에 트리의 정점 개수 $n$ ( $2 \leq n \leq 10^5$ )이 주어진다.

둘째 줄에 $n - 1$ 개의 정수 $p_i$ ( $0 \leq p_i < i$ )가 주어진다. $i$ 번째 값은 정점 $p_i$ 와 정점 $i$ 를 잇는 간선을 나타낸다.

셋째 줄에 $n$ 개의 정수 $a_i$ ( $0 \leq a_i < n$ )가 주어진다. $i$ 번째 값(0부터 셌을 때)은 처음에 $i$ 번 정점에 있는 수이다. $a$ 는 순열이다.

출력

최소 비용을 나타내는 정수 하나를 출력한다.

예제3

예제 1
입력
```
2
0
0 1
```
예상 출력
```
0
```
예제 2
입력
```
2
0
1 0
```
예상 출력
```
1
```
예제 3
입력
```
3
0 0
0 2 1
```
예상 출력
```
2
```