Please read the new rule regarding the restriction on the use of AI tools. It applies starting from round 972. ×

### Roronoa__Zoro's blog

By Roronoa__Zoro, history, 6 weeks ago,

You are given a tree consisting of N nodes. You are also given two arrays A and P of size N each, where the value A[i] denotes the value written on the i th node and the value P[i] denotes that there is an edge between the node i and P[i]. We say that an edge is considered good, if after deleting this edge (this will result in formation of 2 trees), the values in each of the nodes of the trees are distinct . Find the total number of good edges present in tree.

Constraints.

$1 \le N \le 10^{5}$

$1 \le A[i] \le 10^{5}$

$1 \le P[i] \le 10^{5}$

• 0

 » 6 weeks ago, # |   -8 ~~~~~~~~~~import java.util.*;public class Solution { private static List tree; private static int[] values; private static int goodEdges; public static int countGoodEdges(int N, int[] A, int[] P) { tree = new ArrayList<>(N); values = A; goodEdges = 0; for (int i = 0; i < N; i++) { tree.add(new ArrayList<>()); } // Build the tree for (int i = 1; i < N; i++) { tree.get(i).add(P[i]); tree.get(P[i]).add(i); } dfs(0, -1); return goodEdges; } private static Set dfs(int node, int parent) { Set nodeValues = new HashSet<>(); nodeValues.add(values[node]); for (int child : tree.get(node)) { if (child != parent) { Set childValues = dfs(child, node); if (Collections.disjoint(nodeValues, childValues)) { goodEdges++; } nodeValues.addAll(childValues); } } return nodeValues; } public static void main(String[] args) { // Sample Input-1 int N1 = 2; int[] A1 = {1, 1}; int[] P1 = {0, 1}; System.out.println(countGoodEdges(N1, A1, P1)); // Output: 0 // Sample Input-2 int N2 = 4; int[] A2 = {1, 2, 3, 4}; int[] P2 = {0, 1, 2, 3}; System.out.println(countGoodEdges(N2, A2, P2)); // Output: 3 }}~~~~~~~~~~~Try this maybe
•  » » 6 weeks ago, # ^ |   0 It's worst state time complexity is $N{^2}logN$