You are given a rooted tree with n vertices. The vertices are numbered from 1 to n, the…
- User
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
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):
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:
Assistant
We need to compute minimal number of operations to color the tree to target colors. Operations: choose a vertex v and a color x, set all vertices in subtree of v to color x (overwriting). Starting from all zeros. Need to achieve exactly target colors (non-zero). We want minimal steps.
This is like painting the tree from root downwards, we can apply operations that affect whole subtrees. This resembles problem of counting number of "color changes" along paths. Common solution: do DFS from root, keep track of current color of node from ancestors (i.e., after applying operations on ancestors). When visiting node, if its current color (from parent) is not equal to target color, we need to apply an operation at this node to set its subtree to target color. That operation will also set the node itself to target color, and all its descendants will be set accordingly. But then for descendants, their current color becomes the color applied at the nearest ancestor that had an operation. So we can simulate greedy: Starting from root, we have current color (initial 0). For root, if current color != target c[root], we need to paint root's subtree with c[root], so count++. Then we recursively go to children, passing the color that is currently applied (which is the color from the last operation along the path). Actually when we paint at a node, that overwrites any previous color for its subtree. So the current color for a child is: if we performed an operation at the node (the current node), then the child's current color before any operation on child is the color we just painted (i.e., c[node]). If we didn't perform operation at node, then the child's current color is the same as the one passed from parent.
So a simple DFS counting works: For node u, let curColor be the color that has been applied to u from ancestors (i.e., after all operations applied on ancestors). If curColor != c[u], then we need to perform an operation at u, increment answer, and then set curColor = c[u] for its children. Else, we keep curColor unchanged. Then for each child, recursively call with that curColor.
Is this optimal? Usually yes: Because any operation at a node will set its entire subtree to a color. If we need to change the color of node u from its current (inherited) color to target, we must apply an operation at some ancestor (including u) that changes u's color. The most efficient is to apply at u itself, because applying at an ancestor would affect many nodes, possibly causing extra operations to correct others. But could applying at an ancestor sometimes reduce total operations? Suppose u and its siblings have same target color, and parent also has different target, then maybe painting parent with that color could color all children at once. But then parent's target color might be different. Let's think: If parent p's target color is A, child u's target is B. If we paint p with B, then p becomes B (not A), so we need to later repaint p to A? That would be extra steps. So it's generally better to paint nodes at the point where they need to change. The greedy is: If a node's current color doesn't match its target, we must do an operation to change it. The earliest we can do is at that node. Doing at ancestor would also change other nodes, maybe requiring extra operations to revert them. So the greedy is optimal.
Prove: The total number of operations is equal to the number of nodes where the target color differs from the target color of its parent? Not exactly, because if parent and child have same target, and we paint parent with that color, then child automatically becomes correct without extra operation. But in our DFS, if we start at root with curColor=0 (which is not target), we paint root if needed. Then for a child v, if parent p had an operation that set its subtree to c[p], then curColor for v = c[p]. If c[p] == c[v], then we don't need extra operation; else we do. So the answer equals number of nodes where its target color differs from the target color of its nearest ancestor that performed an operation (or root). But equivalently, we can think: Starting from root, we count operations when traversing from parent to child if c[child] != c[parent]? Wait, not exactly: Suppose we have root target=2, child target=2. At root we paint 2 (operation). Then child sees curColor=2 and matches, so no extra operation. So operation count for child is 0. That matches condition c[child]==c[root]? But if root had target=2, but child target=2, and we didn't paint root? But we must paint root because it started 0, so we always paint root if target!=0. So indeed, after root painted, children get curColor=2. So if child's target equals 2, no extra. So for child we need operation only if its target differs from parent's target? But what if parent didn't need an operation because its target equals its own parent's target? Example: root target=1, child1 target=1, child2 target=2. At root we paint 1 (operation). For child1, curColor=1 matches, no operation. For child2, curColor=1 !=2, so operation at child2. So child2's target differs from root's target. But if tree: root target=1, node A (child) target=2, node B (grandchild under A) target=1. At root we paint 1 (operation). At node A, curColor=1 !=2, so we paint A with 2 (operation). Then for B, curColor=2 !=1, so we paint B with 1 (operation). So operations: root, A, B. Compare with c[A]=2, c[root]=1 differ; c[B]=1, c[A]=2 differ. So operation count equals number of edges where parent's target color differs from child's target color? Let's see: edges: root-A: differ, so +1? A-B: differ, +1? But we also have root operation: root itself always counts if c[root]!=0? But 0 is initial color, not a target. So maybe total operations = 1 + number of edges where child's target != parent's target? Check sample 1: tree: vertices: 1-2-? Input: n=6, p: [1,2,2,1,5] meaning: 2's parent=1, 3's parent=2, 4's parent=2, 5's parent=1, 6's parent=5. c: [2,1,1,1,1,1]. So edges and targets: 1(2) - 2(1): differ, 1(2) -5(1): differ, 2(1)-3(1): same, 2(1)-4(1): same, 5(1)-6(1): same. Number of differing edges =2. Add 1? gives 3. That matches answer=3. Sample2: n=7, p: [1,1,2,3,1,4] => edges: 1-2? Actually p2=1, p3=1, p4=2, p5=3, p6=1, p7=4. So tree: 1 connected to 2,3,6; 2 to 4; 3 to5; 4 to7. c: [3,3,1,1,1,2,3] so: node1=3, node2=3, node3=1, node4=1, node5=1, node6=2, node7=3. Differing edges: 1-2: 3vs3 same, 1-3:3vs1 differ, 1-6:3vs2 differ, 2-4:3vs1 differ, 3-5:1vs1 same, 4-7:1vs3 differ. Count=4. Add 1 =5. That matches answer=5. So indeed minimal steps = 1 + number of edges (u,v) where parent's target != child's target, given root must be painted. But careful: what if root's target is 0? Not possible because all target colors >=1. So always at least 1 operation if n>=1? Actually if all nodes target the same color, we need exactly 1 operation (paint root with that color). That matches formula: number of differing edges=0, +1=1. So answer = number of nodes where target color != target color of its parent (considering parent of root as a virtual node with color 0)? Another way: answer = count of vertices v such that c[v] != c[parent[v]] (with c[parent[root]] defined as 0). Since root has parent 0, and c[0]=0 (or not equal to its target always because target >=1), so root always counted. So answer = number of v from 1..n where c[v] != c[parent[v]], where parent[1]=0, c[0]=0. This matches the greedy DFS result.
Let's verify with a more complex scenario: Suppose we have root target=1, child A target=2, child B under A target=2. Then edges: root-A differ, A-B same. So count=1 (root) +1? Actually root is counted because c[root]!=c[0]=0, so root counted. Then A counted because c[A]!=c[root] (2 vs1) => yes. So total 2. But can we do it in 2 operations? Paint root with 1, then paint A with 2 (subtree includes B). That gives A=2, B=2. So 2 operations. Good.
What about scenario where we might avoid painting root? Starting from all 0, we could paint a subtree directly. For root, if we never paint root, its color remains 0, but target is non-zero. So must paint root (or some ancestor, but root has no ancestor). So root must be painted. So answer always at least 1.
Thus solution: read n, parent list, color list. Build children adjacency. Then BFS/DFS from root. For each node, if c[node] != c[parent] (with parent's color, for root compare to 0), increment ans. Print ans.
But wait: check constraints: n up to 1e4, straightforward.
Edge Cases: ensure parent indexing: nodes 2..n given pi. So parent[1] = 0 (or -1). We'll set color[0]=0.
Implementation:
- read n
- read n-1 integers into parent array of size n+1? Actually we can store parent for each node i from 2..n: par[i] = given.
- set par[1] = 0.
- read colors array c[1..n].
- ans = 0.
- loop i from 1 to n: if c[i] != c[par[i]] (with c[0] defined as 0), ans++.
- print ans.
Double-check sample 1: parent[1]=0, c[1]=2, c[0]=0 -> differ -> ans=1. For i=2: parent=1, c2=1 vs c1=2 -> differ -> ans=2. i=3: parent=2, c3=1 vs c2=1 -> same -> ans=2. i=4: parent=2, c4=1 vs c2=1 -> same. i=5: parent=1, c5=1 vs c1=2 -> differ -> ans=3. i=6: parent=5, c6=1 vs c5=1 -> same. =>3. Good.
Sample2: c0=0 -> ans root inc. i=2: par=1, c2=3 vs c1=3 -> same. i=3: par=1, c3=1 vs 3 -> differ. i=4: par=2, c4=1 vs c2=3 -> differ. i=5: par=3, c5=1 vs c3=1 -> same. i=6: par=1, c6=2 vs c1=3 -> differ. i=7: par=4, c7=3 vs c4=1 -> differ. total: root(1)+ differ at 3,4,6,7 =5. Good.
Thus answer is simple.
But is there any nuance? The problem statement says: "It is guaranteed that you have to color each vertex in a color different from 0." So target colors are all non-zero. So indeed root must be painted.
We should ensure we define c[0] = 0.
Thus solution is O(n).
Let's write in Python.
Implementation details:
- read n as int(input())
- read second line: list of n-1 ints -> parents for nodes 2..n.
- build par array: par = [0]*(n+1) ; for i, p in enumerate(parents_input, start=2): par[i] = p
- read colors list: c = [0] + list(map(int, input().split())) # so index 1..n
- ans = 0
- for v in range(1, n+1): if c[v] != c[par[v]]: # par[1] is 0, c[0]=0 ans += 1
- print(ans)
That's all.
But wait: Is this always minimal? Let's double-check more tricky cases: Could there be a scenario where painting at an ancestor could reduce operations even if it temporarily mismatches some nodes but later those mismatches are corrected by further operations, possibly with same or fewer total steps? The greedy algorithm we derived (count of nodes where color differs from parent's target) seems to be correct based on typical solutions for such painting problems (like Codeforces problem "Color the Tree" or similar). However, let's test some cases:
Case: root target=1, child A target=2, child B (under A) target=1. According to formula: edges: root-A differ, A-B differ => count=2? plus root? Actually root counted as differs from 0, so total = 1(root) +1(A) +1(B?) Wait: B's parent is A, c[A]=2, c[B]=1 -> differ, so B counted => total =3. But can we do in 2 operations? Operation1: Paint root with 2? That sets root=2 (but target 1) -> bad. Operation1: Paint A with 1? But then root remains 0? Not possible. Let's attempt: Step1: Paint root with 1 (good, root=1). Step2: Paint A with 2 (sets A=2, B=2). B becomes 2 but target 1, so need step3 to paint B with 1. So 3 steps. Could we do: Step1: Paint A with 1? But A's subtree includes B but not root. Then root remains 0 -> need to paint root later. So Step1: Paint A with 1 (sets A=1, B=1). Then root still 0, target 1. Step2: Paint root with 1 (sets root=1, and also repaints A and B back to 1? Actually painting root with 1 will set all nodes (including A,B) to 1). So after step2, root=1, A=1, B=1. That's target! Wait: That's only 2 steps. Let's simulate:
Initially all 0. Step1: choose v=A, color x=1. Subtree of A (including A and B) become 1. Now: root=0, A=1, B=1. Step2: choose v=1 (root), color x=1. Entire tree becomes 1. Now: root=1, A=1, B=1. Target: root=1, A=2, B=1. A is not 2. So fails: A should be 2 but becomes 1. So that doesn't work.
What if Step1: Paint A with 2, Step2: Paint root with 1? Step1: A=2, B=2. Step2: root=1, A=1, B=1 -> B wrong. So not.
What if Step1: Paint root with 2? Step1: all nodes become 2. Then we need root=1, A=2, B=1. Step2: Paint root with 1? That would set all to 1 -> A becomes 1. Not good. Step2: Paint B with 1? That would set B=1, but root still 2, A=2. Then need step3: Paint root with 1? That would set root=1, A=1, B=1 (B overwritten). So not.
Step1: Paint root with 1. Step2: Paint B with 1? That does nothing. Step2: Paint B with something else? No.
So 3 steps required.
What about scenario: root target=1, child A target=2, child B under A target=2. According to formula: root diff from 0, A diff from root, B same as A => total 2. Two steps: Paint root with 1, then paint A with 2 => works. Could we do it in 1 step? Paint root with 2 => root becomes 2 (target 1) fail. Paint A with 2 => root remains 0 fail. So 2 minimal.
Now consider scenario: root target=2, child A target=1, child B under A target=2. Formula: root diff from 0, A diff from root (1 vs2), B diff from A (2 vs1) => total 3. Is there a 2-step strategy? Attempt: Step1: Paint root with 1 => root=1 (target2 fail). But maybe we can later fix root? Step2: Paint root with 2 => all become 2, then A becomes 2 (target1 fail). Step1: Paint A with 2 => A=2,B=2. root=0. Then step2: Paint root with 2 => all become 2, but A should be 1. Step1: Paint B with 2? Then root=0, A=0, B=2. Step2: Paint root with 2? all 2. A wrong. Step1: Paint root with 2? then A=2,B=2. Need A=1, B=2. Then step2: Paint A with 1 => A=1, B=1 (B wrong). So need step3: Paint B with 2 => then B=2. So 3 steps. So formula holds.
Now more complex: Suppose root target=1, child A target=2, child B (sibling of A) target=2, child C under A target=3. Formula: root (diff from0), A(diff from root), B(diff from root? B target=2 vs root=1 diff, so counted), C: target=3 vs A=2 diff => counted. Total=4. Could we do in fewer? Possibly by painting root with 2? That would set all to 2, then root wrong. Then we need to paint root with 1 -> all become 1, then need to paint C with 3? Not good. Or paint A with 3? Then root=0, A=3, C=3, B=0. Need root=1, B=2, A=2, C=3. Hard.
Maybe we can do: Step1: Paint root with 2 (all 2). Step2: Paint root with 1 (all 1). Not helpful.
Better: Step1: Paint root with 2? Not.
What about: Step1: Paint A with 2 (A=2,C=2). Step2: Paint B with 2 (B=2). Now root=0, but we need root=1. Step3: Paint root with 1 (all 1). Now A=1,B=1,C=1 -> A,B wrong, C wrong. Step4: Paint A with 2? sets A=2,C=2, but then B remains 1. Step5: Paint B with 2. etc. So more.
Maybe step1: Paint A with 3? Then Step2: Paint A with 2? would override. Not.
Thus 4 seems minimal.
But wait, maybe we can do: Step1: Paint root with 1 (root=1). Step2: Paint A with 2 (A=2, C=2). Step3: Paint B with 2 (B=2). Step4: Paint C with 3 (C=3). That's 4 steps. But maybe we can combine: Step1: Paint root with 2 (all 2). Step2: Paint root with 1? That's not helpful.
But could we use operation on a node that is not root nor leaf to color multiple at once? The greedy seems optimal.
Another scenario: root target=1, child A target=1, child B under A target=2. Formula: root diff from0, A same as root (no count), B diff from A => total=2. Steps: Paint root with 1 (all 1). Then B is 1 but needs 2, so paint B with 2 -> subtree of B (just B) becomes 2. That's 2 steps. Could we do 1 step? Painting root with 2 gives B=2 but root wrong. Painting A with 2 gives A=2,B=2 but root 0. So at least 2.
All good.
Thus formula stands.
We must be careful: The problem statement says "It is guaranteed that you have to color each vertex in a color different from 0." So all target colors are non-zero, but they could be any from 1 to n (n up to 1e4). So fine.
Now we can implement.
Potential pitfalls: Input reading: second line contains n-1 integers; third line contains n integers. Ensure we handle large input quickly; Python's input is fine.
But wait, is the simple answer always correct for all trees? Let's reason more formally.
Consider any sequence of operations. Each operation paints a whole subtree with a color. The final coloring must match target. We can think of the set of operations as painting over each other, with later operations overriding earlier ones for nodes in their subtree. So the final color of a node is the color of the last operation applied on that node or any of its ancestors. In other words, if we consider the operations in order, the final color of node u is the color of the operation with deepest (closest to u) vertex among those operations that are ancestors of u (including u) that is applied last in time? Actually operations can be in any order, and later operations overwrite previous ones. So for each node, the final color is determined by the latest operation among those whose chosen vertex v is an ancestor of the node (including itself). Because that operation sets the entire subtree of v, which includes the node. So if we have a list of operations (v_i, color_i) in chronological order, then for a node u, find the last i such that v_i is ancestor of u; then c_u = color_i. If no such operation, then c_u = 0.
Thus we need to assign to each node u a "responsible" operation that gives its final color. Since operations are whole subtrees, the responsible operation for a node must be such that its vertex is an ancestor of u, and its color is target[u]. Also, the set of operations must be consistent across nodes: if two nodes share the same responsible operation, they must have same target color. Moreover, the responsible operation's vertex defines a partition of the tree: Each operation at vertex v sets the color for all nodes in its subtree, except those that are later overwritten by operations in deeper subtrees. So the final set of responsible operations correspond to a set of nodes S such that no two nodes in S are ancestor/descendant (since if you have two operations, one ancestor of the other, the deeper one overwrites the ancestor's effect on its subtree, so the ancestor's operation is not the responsible for nodes in that subtree. For a node to be responsible (i.e., its operation is the last affecting its descendants), it must not have any descendant operation that overwrites it. But there could be operations on unrelated branches. So the set of nodes at which we perform operations must be such that they are "lowest" in the sense that no two are on the same path from root? Actually if we perform operations at both node v and its descendant w, then the operation at w will overwrite the operation at v for w's subtree, so for nodes in w's subtree, the responsible operation is w, not v. For nodes in v's subtree but outside w's subtree, the responsible operation remains v. So it's allowed to have ancestor and descendant operations, but they apply to disjoint sets of nodes (the descendant's subtree is overwritten). So the set of nodes where we perform operations can be any set; but to minimize number of operations, we would avoid redundant operations (i.e., operations that do not affect the final coloring, or operations that could be merged). The greedy algorithm essentially selects the minimal set of nodes: for each node, if its target color differs from the color it would inherit from its parent (i.e., the color from the nearest ancestor operation), then we must perform an operation at that node to set its color correctly. Because if we don't perform at node u, then the color of u must come from some ancestor operation. That ancestor operation would set the same color to u and its siblings, etc. But since u's target may differ from its parent's target (or from the ancestor's color), unless some ancestor operation sets exactly u's target, we would need to perform at u. Could we instead perform an operation at an ancestor that sets a color that matches both u and its parent? But if parent and child have different target colors, no single color can satisfy both. So an ancestor operation can only set one color; if it sets the child's target, then parent would get that color, which would be wrong unless we later change parent? But that would require an operation at parent (or another ancestor) to change it, potentially causing more operations. The greedy approach seems optimal.
The known solution for Codeforces problem 163A? Actually this problem is from Codeforces Round #... I recall problem "Color the Tree" maybe from #... But the solution is exactly to count the number of vertices where c[v] != c[parent[v]].
Thus the answer is straightforward.
Implementation in Python:
def solve(): import sys input = sys.stdin.readline n = int(input()) parents_input = list(map(int, input().split())) par = [0]*(n+1) for i, p in enumerate(parents_input, start=2): par[i] = p colors = [0] + list(map(int, input().split())) ans = 0 for v in range(1, n+1): if colors[v] != colors[par[v]]: ans += 1 print(ans)
That's all.
But is there any case where the root's parent is 0 and color[0] defined as 0 always works? Yes because root's target is non-zero, so always counts. But what if root's target is 0? Not allowed.
Time O(n), memory O(n).
Now produce final answer.
We'll provide explanation in final output.
But the user asked: "You are given a rooted tree... Print a single integer — the minimum number of steps you have to perform to color the tree into given colors." So we need to output just the integer.
Make sure to handle input reading properly. The second line contains n-1 integers, but sometimes there may be extra spaces or lines? We'll use split.
Edge case: n=2? Works.
Thus final answer.
But as ChatGPT, we should output the solution code in python.
However, the platform might require a full solution with defined solve() and main. We'll provide.
We'll also note that this is a Codeforces problem 902B? Actually I recall problem 902B "Coloring a Tree" or something. The solution is exactly count differences.
We'll produce final answer.
Now produce final response with explanation and code. ```python
import sys
def solve() -> None: data = sys.stdin.read().strip().split() if not data: return it = iter(data) n = int(next(it)) parent = [0] * (n + 1) # parent[1] = 0 for i in range(2, n + 1): parent[i] = int(next(it)) color = [0] * (n + 1) for i in range(1, n + 1): color[i] = int(next(it))
ans = 0 # colour of the virtual parent of the root is 0 for v in range(1, n + 1): if color[v] != color[parent[v]]: ans += 1 print(ans)if name == "main": solve()