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 c_{v}. Initially c_{v} = 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 c_{u} = 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 ≤ 10^4) — the number of vertices in the tree.

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

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.

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
6
1 2 2 1 5
2 1 1 1 1 1

Output
3

Input
7
1 1 2 3 1 4
3 3 1 1 1 2 3

Output
5



-----Note-----

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

$A$

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

[Image]

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

[Image]

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

[Image]

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

[Image]

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

[Image]

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

$8$

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

[Image]

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

[Image]

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

[Image]

Difficulty: interview

Starter code:

Solutions:


n = int(input())

T = [int(x) for x in input().split()]

C = [int(x) for x in input().split()]

T_inv = [[] for _ in range(n)]

for i in range(n - 1):
    T_inv[T[i] - 1] += [i + 1]

result = 1

#for i in range(n):
#    print(T_inv[i])

for i in range(n):
    for child in T_inv[i]:
        if C[i] != C[child]:
            result += 1

print(result)


n = int(input())
es = list(map(int, input().split()))
g = [[] for i in range(n)]
for i, e in enumerate(es):
    g[i+1].append(e-1)
    g[e-1].append(i+1)
cols = list(map(int, input().split()))
ans = 0
q = [[0, 0]]
vis = set([0])
while len(q) > 0:
    v, c = q[0][0], q[0][1]
    del q[0]
    nc = cols[v]
    if nc != c:
        ans += 1
    for u in g[v]:
        if u not in vis:
            vis.add(u)
            q.append([u, nc])
print(ans)

import sys
sys.setrecursionlimit(1000000)
read = sys.stdin.readline

n = int(read())
parent = [1] + list(map(int, read().split()))
color = list(map(int, read().split()))
underVertex = [[] for _ in range(n+1)]

for i, p in enumerate(parent):
	if i+1 != p:
		underVertex[p] += [i+1]


def dfs(idx, c):
	count = 0
	if c != color[idx-1]:
		count = 1
	for nxt in underVertex[idx]:
		count += dfs(nxt, color[idx-1])
	return count

print(dfs(1, 0))

n = int(input())

children = [[] for _ in range(n)]
ps = [int(v) for v in input().split()]

for i, p in enumerate(ps, 1):
    children[p - 1].append(i)

cs = [int(v) for v in input().split()]

ans = 0

# vertex, color
stack = [(0, 0)]
while stack:
    v, c = stack.pop()
    if c != cs[v]:
        ans += 1
        c = cs[v]
    for child in children[v]:
        stack.append((child, c))

print(ans)


def bfs(endcolor):
    color=[0]*(n+1)
    endcolor=[0]+endcolor
    count=0
    visited, queue = set(), [1]
    while queue:
        #print(color,queue,count)
        vertex = queue.pop(0)
        if endcolor[vertex] != color[vertex]:
            color[vertex]=endcolor[vertex]
            count+=1
        if vertex not in visited:
            visited.add(vertex)
            queue.extend(g[vertex] - visited)
            for x in g[vertex] - visited:
                color[x]=color[vertex]
    return count
n=int(input())
g={x:set() for x in range(1,n+2)}
i=1
for x in map(int,input().split()):
    i+=1
    g[x].add(i)
    #g[i].add(x)
#print(g)
print(bfs(list(map(int,input().split()))))

n = int(input())
p = [0] + list(map(int, input().split()))
c = [0] + list(map(int, input().split()))
res = 1
mp = {i:[] for i in range(1, n + 1)}
for i in range(1, len(p)):
	mp[p[i]].append(i + 1)
col = {i:0 for i in range(1, n + 1)}
q = [1]
while q != []:
	cur = q.pop(0)
	for i in mp[cur]:
		q.append(i)
	if cur == 1:
		col[cur] = c[cur]
	else:
		col[cur] = col[p[cur - 1]]
		if col[cur] != c[cur]:
			col[cur] = c[cur]
			res += 1
print(res)

from collections import deque

n = int(input())
adj = [[] for i in range(n + 1)]
for i, x in enumerate(input().split()):
    i += 2
    x = int(x)
    adj[i].append(x)
    adj[x].append(i)

parents = [0 for i in range(n + 1)]
parents[1] = -1

# print(adj)

colors = [-1] + [int(x) for x in input().split()]

q = deque([1])
while len(q) > 0:
    node = q.popleft()
    for x in adj[node]:
        if parents[x] == 0:
            parents[x] = node
            q.append(x)

# print(parents)

ans = 1

for i in range(2, n + 1):
    if colors[i] != colors[parents[i]]:
        ans += 1

print(ans)

n = int(input())
a = list(map(int,input().split()))
b = list(map(int,input().split()))
ans = 1
for i in range(n - 1):
    if b[i+1] != b[a[i]-1]:
        ans += 1
print(ans)

n = int(input())

p = [int(i) for i in input().split()]
c = [int(i) for i in input().split()]
ans = 1;
ind = 1

for i in p:
    if c[i-1]!=c[ind]:
        ans+=1;
    ind+=1 
    
print(ans)

n = int(input().strip())
p = [int(x) for x in input().split()]
c = [int(x) for x in input().split()]
moves = 1
for i in range(1,n):
    if c[p[i-1]-1]!=c[i]:
        moves+=1
print(moves)

n=int(input())
p=list(map(int,input().split()))
c=list(map(int,input().split()))


nbr=1
for i in range(1,n):
    if c[i]!=c[p[i-1]-1]:
        nbr+=1

print(nbr)

    
    
    


from collections import defaultdict as di
from collections import deque as dq
n=int(input())
coupl = di(list)
nodess = [int(x)-1 for x in input().split()]
for i in range(n-1):
    node = nodess[i]
    coupl[i+1].append(node)
    coupl[node].append(i+1)

colors = [int(x)-1 for x in input().split()]

Q=dq()
found=set()
Q.append((0,0))
parent = [-1]*n
order = []
while Q:
    node,p = Q.popleft()
    if node in found:
        continue
    found.add(node)
    parent[node]=p
    order.append(node)
    for nei in coupl[node]:
        Q.append((nei,node))

color = [-1]*n
count = 0
for node in order:
    if colors[node]==color[parent[node]]:
        pass
    else:
        count+=1
    color[node]=colors[node]

print(count)


n=int(input())
l=[0]
s=0
l.extend([int(i)-1 for i in input().split()])
m=[int(i) for i in input().split()]
cv=[0]*n
if m[0]!=0:
    cv[0]=m[0]
    s+=1
for i in range(n):
    if m[i]!=cv[l[i]]:
        cv[i]=m[i]
        s+=1
    else:
        cv[i]=cv[l[i]]  
print(s)

n = int(input())
P = [0]+list(map(lambda c:int(c)-1,input().split()))
C = list(map(int,input().split()))

cnt = sum(C[i]==C[p] for i,p in enumerate(P))

print(n-cnt+1)

N = int(input())
con = [0]
vert = [i for i in range(1,N+1)]
a = input().split(" ")
for i in range(N-1):
    con.append(int(a[i])-1)
color=[]
a = input().split(" ")
for i in range(N):
    color.append(int(a[i]))
cur = [color[0] for i in range(N)]
steps=1
for i in range(1,N):
    if cur[con[i]]==color[i]:
        cur[i] = color[i]
    else:
        steps+=1
        cur[i] = color[i]
print(steps)
#print(con)
#print(color)
#print(vert)


n = int(input())


e = [int(i)-1 for i in input().split()]
v = [int(i) for i in input().split()]
counter = 1

for i in range(n-1):
    if v[e[i]] != v[i+1]:
        counter+=1
        
print(counter)

n = int(input())
s = input()
ss = input()
tree = [[1]]
p = list(map(int, s.split()))
q = list(map(int, ss.split()))
for i in range(0, n-1):
    tree.append([i+2])
    tree[p[i]-1].append(i+2)
count = 0
for each in tree:
    if len(each) == 1:
        tree.remove(each)
        count += 1
tree.sort(key=len)
for each in tree:
    sub = list(map(lambda x:q[x-1], each[1:]))
    count += (1-sub.count(q[each[0]-1]))
print(count)

n = int(input())
p = list(map(int,input().split()))
c = list(map(int,input().split()))
k = 1
for i in range(n-1):
    if c[i+1] != c[p[i]-1]:
        k+= 1
print(k)

def pst(root, curr):
    nonlocal times
    if cs[root-1] != curr:
        times += 1
    curr = cs[root-1]
    if root not in vss:
        return
    chn = vss[root]
    for ch in chn:
        pst(ch, curr)


n = int(input())
vs = [int(x) for x in input().split()]

cs = [int(x) for x in input().split()]



# vss = set()
# for i in range(2, n + 1):
#     vss.add((vs[i - 2], i))
#
# vsbp = {v[0]: v for v in vss}
vss = {}
for c, p in enumerate(vs):
    if not p in vss:
        vss[p] = [c+2]
    else:
        vss[p].append(c+2)

times = 0

def flattened():
    times = 0
    root = 1
    curr = 0

    firstpart = True

    stack = []
    while True:


        if firstpart:

            if cs[root-1] != curr:
                times += 1
            curr = cs[root - 1]
            if root not in vss:
                firstpart = False
                if len(stack) == 0:
                    print(times)
                    return
                chni, curr = stack.pop()
            else:
                chn = vss[root]
                chni = iter(chn)

        try:
            ch = next(chni)
            firstpart = True
            root = ch
            stack.append((chni, curr))
        except StopIteration:
            firstpart = False
            if len(stack) == 0:
                print(times)
                return
            chni, curr = stack.pop()



        # if root in vss:
        #     chn = vss[root]
        #     chni = iter(chn)
        #     stack.append((curr, chni))
        # else:
        #     if len(stack) == 0:
        #         print(times)
        #         return


# pst(1, 0)
# print(times)

flattened()


def main():
	n = int(input())
	parents = [int(x)-1 for x in input().strip().split()]
	colors = [int(x) for x in input().strip().split()]
	
	ans = 1

	for i in range(n-1):
		c = i+1
		p = parents[i]
		if (colors[c] != colors[p]):
			ans += 1

	print(ans)
	
def __starting_point():
	main()
__starting_point()

n = int(input())
mps = list(map(int,input().split()))
col = list(map(int,input().split()))
st = 2
par = dict()
for i in range(n-1):
	par[st] = par.get(st,[])
	par[st].append(mps[i])
	par[mps[i]] = par.get(mps[i],[])
	par[mps[i]].append(st)
	st+=1

queue = [1]
vis = [0]*(n+1)
ans = 1
while len(queue):
	s = queue.pop(0)
	vis[s] = 1
	for i in par[s]:
		if not vis[i]:
			queue.append(i)
			vis[i] = 1
			if col[i-1]!=col[s-1]:
				ans+=1

print(ans)

n = int(input())
graph = [[] for i in range(n)]
l = list(map(int, input().split(" ")))
for i in range(n-1):
    graph[i+1] += [l[i]-1]
    graph[l[i]-1] += [i+1]
cc = list(map(int, input().split(" ")))
# for i in range(n):
#     print (graph[i])
ll = list(range(n))
colors = [0 for i in range(n)]
counter = 0
visited = [False for i in range(n)]
ans = 0
counter = 0
q = [i]
visited[i] = True
while(len(q) != 0):
    u = q[0]
    # print ("u: ", u)
    q.pop(0)
    for j in graph[u]:
        # print (j)
        if (visited[j]):
            continue
        if(cc[j] != cc[u]):
            counter+=1
        visited[j] = True
        q += [j]
print(counter+1)


import sys

lines = []
for line in sys.stdin:
    lines.append(line.rstrip("\r\n\t "))
n = int(lines[0])
data = lines[1].split(' ')
tree = [0]
for x in data:
    tree.append(int(x))
data = lines[2].split(' ')
colors = [int(data[0])]
operations = 1
for i in range(n):
    if i > 0:
        color = int(data[i])
        parent = tree[i]
        if colors[parent - 1] != color:
            operations += 1
        colors.append(color)
print(operations)


n=int(input())
pi=list(map(int,input().split()))
ci=list(map(int,input().split()))
com=1
for i in range(1,n):
      if ci[i]!=ci[pi[i-1]-1]:
            com+=1
print(com)