Problem D. Coloring a Tree

时间限制 2 ms   内存限制 256 MB

You are given a rooted tree with n vertices. The vertices are numbered from 1 to n, the root is the vertex number 1.

Each vertex has a color, let's denote the color of vertex v by cv. Initially cv = 0.

You have to color the tree into the given colors using the smallest possible number of steps. On each step you can choose a vertex v and a color x, and then color all vectices in the subtree of v (including v itself) in color x. In other words, for every vertex u, such that the path from root to u passes through v, set cu = x.

It is guaranteed that you have to color each vertex in a color different from 0.

You can learn what a rooted tree is using the link: https://en.wikipedia.org/wiki/Tree_(graph_theory).

输入数据

The first line contains a single integer n (2 ≤ n ≤ 104) — the number of vertices in the tree.

The second line contains n - 1 integers p2, p3, ..., pn (1 ≤ pi < i), where pi means that there is an edge between vertices i and pi.

The third line contains n integers c1, c2, ..., cn (1 ≤ ci ≤ n), where ci is the color you should color the i-th vertex into.

It is guaranteed that the given graph is a tree.

输出数据

Print a single integer — the minimum number of steps you have to perform to color the tree into given colors.

样例

样例说明

The tree from the first sample is shown on the picture (numbers are vetices' indices):

bf595baf9a7f72318b1260874e9bc10c23a5d28e.png

On first step we color all vertices in the subtree of vertex 1 into color 2 (numbers are colors):

6e6278cf1509a56a697f1a06c544a927c2b93d9c.png

On seond step we color all vertices in the subtree of vertex 5 into color 1:

fe162c1660e424f6f9dbab7771a4fcd25da6abd3.png

On third step we color all vertices in the subtree of vertex 2 into color 1:

f1c5964a6d396891358eb8d7f3e1305815b77874.png

The tree from the second sample is shown on the picture (numbers are vetices' indices):

9d2ec4dbbf4473b31a1feb04a05b4f13cd3cb5cf.png

On first step we color all vertices in the subtree of vertex 1 into color 3 (numbers are colors):

6f56fb56f1a4aa052c310f592b4a9ac8df2fd451.png

On second step we color all vertices in the subtree of vertex 3 into color 1:

02e329217066c53b36bf2de2c9683ffbecfe0a85.png

On third step we color all vertices in the subtree of vertex 6 into color 2:

06655c37868706b3fb3959b47faae8e7c001403c.png

On fourth step we color all vertices in the subtree of vertex 4 into color 1:

f9d8c0208ed406c6a62eeca9a88722f798789cbf.png

On fith step we color all vertices in the subtree of vertex 7 into color 3:

6a04df7ac110d0425d1193edefe7e93350192b7e.png

提交

请先 登录

© 2025 FAQs Contact About