Roronoa__Zoro's blog

Can anyone explain "small-large" merging or any other technique for this problem ?
By Roronoa__Zoro, history, 4 months ago, In English

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

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
4 months ago, # |
  Vote: I like it -8 Vote: I do not like it

~~~~~~~~~~

import java.util.*;

public class Solution { private static List<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<Integer> dfs(int node, int parent) {
    Set<Integer> nodeValues = new HashSet<>();
    nodeValues.add(values[node]);

    for (int child : tree.get(node)) {
        if (child != parent) {
            Set<Integer> 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

→ Reply