| Codeforces Round 453 (Div. 2) |
|---|
| Закончено |
Задано корневое дерево, состоящее из n вершин. Будем считать, что вершины дерева пронумерованы целыми числами от 1 до n. Корнем дерева является вершина с номером 1.
Каждая вершина дерева имеет определенный цвет, цвет вершины v будем обозначать cv, изначально cv = 0.
В задаче вам требуется раскрасить дерево в заданные цвета с помощью минимального числа действий. За одно действие вы можете выбрать вершину v и цвет x, и покрасить все вершины поддерева v (включая v) в цвет x, то есть для всех вершин u таких, что путь от корня до u содержит вершину v, сделать cu = x.
Гарантируется, что все вершины надо покрасить в цвет, отличный от 0.
Определение корневого дерева можно прочитать по ссылке: https://ru.wikipedia.org/wiki/Дерево_(теория_графов).
В первой строке находится одно целое число n (2 ≤ n ≤ 104) — число вершин дерева.
В следующей строке следуют n - 1 целых чисел p2, p3, ..., pn (1 ≤ pi < i), где pi обозначает, что существует ребро в графе между вершинами i и pi.
В следующей строке следуют n целых чисел c1, c2, ..., cn (1 ≤ ci ≤ n), где ci обозначает желаемый цвет вершины i.
Гарантируется, что заданный граф является деревом.
На первой и единственной строке выведите одно целое число — минимальное число действий, за которое можно покрасить дерево в желаемые цвета.
6
1 2 2 1 5
2 1 1 1 1 1
3
7
1 1 2 3 1 4
3 3 1 1 1 2 3
5
Первый пример расположен на следующей картинке (числа обозначают номера вершин):
Первым действием мы красим все вершины поддерева вершины 1 в цвет 2 (числа обозначают цвета):
Вторым действием мы красим все вершины поддерева вершины 5 в цвет 1:
Третьим действием мы красим все вершины поддерева вершины 2 в цвет 1:
Второй пример расположен на следующей картинке (числа обозначают номера вершин):
Первым действием мы красим все вершины поддерева вершины 1 в цвет 3 (числа обозначают цвета):
Вторым действием мы красим все вершины поддерева вершины 3 в цвет 1:
Третьим действием мы красим все вершины поддерева вершины 6 в цвет 2:
Четвертым действием мы красим все вершины поддерева вершины 4 в цвет 1:
Пятым действием мы красим все вершины поддерева вершины 7 в цвет 3:
