409151: GYM103447 C Colorful Tree

Memory Limit:512 MB Time Limit:0 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

C. Colorful Treetime limit per test1.0 smemory limit per test512 megabytesinputstandard inputoutputstandard output

Given a 1-rooted tree $$$T$$$, where there is a desired color $$$c_u$$$ for each leaf(vertices who have no children) $$$u$$$. The leaves have no color initially, and you should do several operations to make all the leaves painted by their desired colors. For each operation, you can choose a vertex $$$x$$$ and a color $$$c$$$, then make all the leaves in the $$$x$$$-rooted subtree painted by color $$$c$$$. Specially, if a leaf was painted multiple times, only the latest painted color counts. Determine the minimum possible number of operations to make all the leaves painted by their desired colors.

Input

The first line contains one integer $$$n\,(1\le n \le 10^5)$$$, denoting the size of the tree.

The second line contains $$$n-1$$$ integers $$$p_1, p_2, \cdots, p_{n-1} \, (1\le p_i \le i)$$$, where $$$p_i$$$ denotes the parent of vertex $$$i+1$$$.

The third line contains $$$n$$$ integers $$$c_1, c_2, \cdots, c_n \, (0 \le c_i \le n)$$$, denoting the desired colors, where $$$c_i \neq 0$$$ iff vertex $$$i$$$ is leaf.

Output

Output one line containing one integer, denoting the answer.

ExamplesInput
7
1 1 2 2 3 3
0 0 0 1 1 1 2
Output
2
Input
7
1 1 2 2 3 3
0 0 0 1 2 1 2
Output
3
Note

For the second test case, one possible scheme is:

  1. Choose $$$x = 1, c = 1$$$, the colors become $$$\{0, 0, 0, 1, 1, 1, 1\}$$$ respectively.
  2. Choose $$$x = 7, c = 2$$$, the colors become $$$\{0, 0, 0, 1, 1, 1, 2\}$$$ respectively.
  3. Choose $$$x = 5, c = 2$$$, the colors become $$$\{0, 0, 0, 1, 2, 1, 2\}$$$ respectively.

加入题单

上一题 下一题 算法标签: