codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

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 ![](https://espresso.codeforces.com/f543b5881f8f90906c7fb8c0dae62f2443b92ea1.png)
     80 
     81 On first step we color all vertices in the subtree of vertex 1 into color 2 (numbers are colors):
     82 
     83 ![](https://espresso.codeforces.com/1c7bb267e2c1a006132248a43121400189309e2f.png)
     84 
     85 On seond step we color all vertices in the subtree of vertex 5 into color 1:
     86 
     87 ![](https://espresso.codeforces.com/2201a6d49b89ba850ff0d0bdcbb3f8e9dd3871a8.png)
     88 
     89 On third step we color all vertices in the subtree of vertex 2 into color 1:
     90 
     91 ![](https://espresso.codeforces.com/6fa977fcdebdde94c47695151e0427b33d0102c5.png)
     92 
     93 The tree from the second sample is shown on the picture (numbers are vetices' indices):
     94 
     95 ![](https://espresso.codeforces.com/d70f9ae72a2ed429dd6531cac757e375dd3c953d.png)
     96 
     97 On first step we color all vertices in the subtree of vertex 1 into color 3 (numbers are colors):
     98 
     99 ![](https://espresso.codeforces.com/7289e8895d0dd56c47b6b17969b9cf77b36786b5.png)
    100 
    101 On second step we color all vertices in the subtree of vertex 3 into color 1:
    102 
    103 ![](https://espresso.codeforces.com/819001df7229138db3a407713744d1e3be88b64e.png)
    104 
    105 On third step we color all vertices in the subtree of vertex 6 into color 2:
    106 
    107 ![](https://espresso.codeforces.com/80ebbd870a0a339636a21b9acdaf9de046458b43.png)
    108 
    109 On fourth step we color all vertices in the subtree of vertex 4 into color 1:
    110 
    111 ![](https://espresso.codeforces.com/ed836aa723ac0176abde4e32988e3ac205014e93.png)
    112 
    113 On fith step we color all vertices in the subtree of vertex 7 into color 3:
    114 
    115 ![](https://espresso.codeforces.com/8132909e11b41c27b8df2f0b0c10bc841f35e58a.png)