902B.md (3421B)
1 Source: https://codeforces.com/problemset/problem/902/B 2 3 B. Coloring a Tree 4 5 time limit per test 6 7 1 second 8 9 memory limit per test 10 11 256 megabytes 12 13 input 14 15 standard input 16 17 output 18 19 standard output 20 21 You are given a rooted tree with *n* vertices. The vertices are numbered from 1 to *n*, the root is the vertex number 1. 22 23 Each vertex has a color, let's denote the color of vertex *v* by *c**v*. Initially *c**v* = 0. 24 25 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 *c**u* = *x*. 26 27 It is guaranteed that you have to color each vertex in a color different from 0. 28 29 You can learn what a rooted tree is using the link: <https://en.wikipedia.org/wiki/Tree_(graph_theory)>. 30 31 Input 32 33 The first line contains a single integer *n* (2 ≤ *n* ≤ 104) — the number of vertices in the tree. 34 35 The second line contains *n* - 1 integers *p*2, *p*3, ..., *p**n* (1 ≤ *p**i* < *i*), where *p**i* means that there is an edge between vertices *i* and *p**i*. 36 37 The third line contains *n* integers *c*1, *c*2, ..., *c**n* (1 ≤ *c**i* ≤ *n*), where *c**i* is the color you should color the *i*-th vertex into. 38 39 It is guaranteed that the given graph is a tree. 40 41 Output 42 43 Print a single integer — the minimum number of steps you have to perform to color the tree into given colors. 44 45 Examples 46 47 Input 48 49 ``` 50 6 51 1 2 2 1 5 52 2 1 1 1 1 1 53 ``` 54 55 Output 56 57 ``` 58 3 59 ``` 60 61 Input 62 63 ``` 64 7 65 1 1 2 3 1 4 66 3 3 1 1 1 2 3 67 ``` 68 69 Output 70 71 ``` 72 5 73 ``` 74 75 Note 76 77 The tree from the first sample is shown on the picture (numbers are vetices' indices): 78 79  80 81 On first step we color all vertices in the subtree of vertex 1 into color 2 (numbers are colors): 82 83  84 85 On seond step we color all vertices in the subtree of vertex 5 into color 1: 86 87  88 89 On third step we color all vertices in the subtree of vertex 2 into color 1: 90 91  92 93 The tree from the second sample is shown on the picture (numbers are vetices' indices): 94 95  96 97 On first step we color all vertices in the subtree of vertex 1 into color 3 (numbers are colors): 98 99  100 101 On second step we color all vertices in the subtree of vertex 3 into color 1: 102 103  104 105 On third step we color all vertices in the subtree of vertex 6 into color 2: 106 107  108 109 On fourth step we color all vertices in the subtree of vertex 4 into color 1: 110 111  112 113 On fith step we color all vertices in the subtree of vertex 7 into color 3: 114 115 