Algorithm


B. Coloring a Tree
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

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).

Input

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.

Output

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

Examples
input
Copy
6
1 2 2 1 5
2 1 1 1 1 1
output
Copy
3
input
Copy
7
1 1 2 3 1 4
3 3 1 1 1 2 3
output
Copy
5
Note

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

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

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

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

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

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

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

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

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

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

 

Code Examples

#1 Code Example with C++ Programming

Code - C++ Programming

#include <bits/stdc++.h>

using namespace std;

int const N = 1e4 + 1;
int c[N];
bool vis[N];
vector<vector<int> > g;

int dfs(int cur, int prv) {
	vis[cur] = true;

	int res = (prv != c[cur]);
	for(int i = 0; i < g[cur].size(); ++i)
		if(!vis[g[cur][i]])
			res += dfs(g[cur][i], c[cur]);

	return res;
}

int main() {
	int n;
	scanf("%d", &n);

	g.resize(n);

	for(int i = 1, tmp; i < n; ++i) {
		scanf("%d", &tmp);
		g[--tmp].push_back(i);
	}

	for(int i = 0; i < n; ++i)
		scanf("%d", c + i);

	printf("%d\n", dfs(0, -1));

	return 0;
}
Copy The Code & Try With Live Editor

Input

x
+
cmd
6
1 2 2 1 5
2 1 1 1 1 1

Output

x
+
cmd
3
Advertisements

Demonstration


Codeforces Solution-Coloring a Tree-Solution in C, C++, Java, Python

Previous
Codeforces solution 1080-B-B. Margarite and the best present codeforces solution
Next
CodeChef solution DETSCORE - Determine the Score CodeChef solution C,C+