Найти все вторые пути данного графа

Это вопрос для собеседования. У меня есть неориентированный граф с n узлами из 1 to n. На графике нет циклов.

Граф представлен двумя списками: списком from и списком to. Ребро соединяет точки from[i] to to[i].

Предположим, что максимальное расстояние между любыми двумя узлами равно max.

Теперь узел считается первичным, если он лежит на простом пути между двумя узлами u и v так, что расстояние между u и v равно max. Все остальные узлы являются вторичными.

Теперь найдите сумму индексов всех второстепенных узлов. Эта сумма является ожидаемым решением.

Example n = 4 
from = [1, 1, 2] 
to = [2, 3, 4]

Answer : 0

Объяснение:

The maximum distance between any two nodes is 3, the pair (3, 4). All the nodes on the path 3 --> 1 --> 2 --> 4 are primary. Since no node is secondary, the answer is 0.

Другие тестовые случаи:

node = 6
from = [1,1,1,2,3]
to  [2,3,4,5,6]

Answer :
4


nodes = 5
from = [1,1,2,2]
to  [2,3,4,5]

Answer :
0

Вот мой код, который я пробовал:

import java.util.*;

public class Main {
    
    public static long solution(int n, List<Integer> from, List<Integer> to) {
        List<List<Integer>> adjList = new ArrayList<>();
        for (int i = 0; i <= n; i++) {
            adjList.add(new ArrayList<>());
        }
        
        // Build adjacency list
        for (int i = 0; i < from.size(); i++) {
            adjList.get(from.get(i)).add(to.get(i));
            adjList.get(to.get(i)).add(from.get(i));
        }
        
        // First DFS/BFS to find the farthest node from any node (let's start with node 1)
        int[] dist = bfs(1, n, adjList);
        int farthest1 = findFarthestNode(dist);
        
        // Second DFS/BFS to find the farthest node from farthest1
        dist = bfs(farthest1, n, adjList);
        int farthest2 = findFarthestNode(dist);
        int mx = dist[farthest2];
        
        // DFS/BFS to find all primary nodes on the path from farthest1 to farthest2
        Set<Integer> primaryNodes = findPrimaryNodes(farthest1, farthest2, n, adjList);
        
        // Sum of secondary influencer indices
        long secondarySum = 0;
        for (int i = 1; i <= n; i++) {
            if (!primaryNodes.contains(i)) {
                secondarySum += i;
            }
        }
        
        return secondarySum;
    }
    
    // BFS function to calculate distances from a start node
    private static int[] bfs(int start, int n, List<List<Integer>> adjList) {
        int[] dist = new int[n + 1];
        Arrays.fill(dist, -1);
        Queue<Integer> queue = new LinkedList<>();
        
        queue.add(start);
        dist[start] = 0;
        
        while (!queue.isEmpty()) {
            int node = queue.poll();
            for (int neighbor : adjList.get(node)) {
                if (dist[neighbor] == -1) {
                    dist[neighbor] = dist[node] + 1;
                    queue.add(neighbor);
                }
            }
        }
        
        return dist;
    }
    
    // Function to find the farthest node given distances
    private static int findFarthestNode(int[] dist) {
        int maxDist = 0;
        int node = 0;
        for (int i = 1; i < dist.length; i++) {
            if (dist[i] > maxDist) {
                maxDist = dist[i];
                node = i;
            }
        }
        return node;
    }
    
    // DFS/BFS to find all primary nodes on the path from farthest1 to farthest2
    private static Set<Integer> findPrimaryNodes(int farthest1, int farthest2, int n, List<List<Integer>> adjList) {
        Set<Integer> primaryNodes = new HashSet<>();
        Stack<Integer> stack = new Stack<>();
        boolean[] visited = new boolean[n + 1];
        int[] parent = new int[n + 1];
        
        stack.push(farthest1);
        visited[farthest1] = true;
        parent[farthest1] = -1;
        
        while (!stack.isEmpty()) {
            int node = stack.pop();
            for (int neighbor : adjList.get(node)) {
                if (!visited[neighbor]) {
                    parent[neighbor] = node;
                    visited[neighbor] = true;
                    stack.push(neighbor);
                    if (neighbor == farthest2) {
                        // Trace back to find the path from farthest2 to farthest1
                        int current = farthest2;
                        while (current != -1) {
                            primaryNodes.add(current);
                            current = parent[current];
                        }
                        return primaryNodes;
                    }
                }
            }
        }
        return primaryNodes;
    }

    public static void main(String[] args) {
        List<Integer> from = Arrays.asList(1, 1, 2);
        List<Integer> to = Arrays.asList(2, 3, 4);
        System.out.println(solution(4, from, to)); // Output: 0

        from = Arrays.asList(1, 1, 1, 2, 3);
        to = Arrays.asList(2, 3, 4, 5, 6);
        System.out.println(solution(6, from, to)); // Output: 4

        from = Arrays.asList(1, 1, 2, 2);
        to = Arrays.asList(2, 3, 4, 5);
        System.out.println(solution(5, from, to)); // Output: 0
    }
}

Я попробовал подход BFS, мой код не работает в третьем тестовом примере, вместо того, чтобы выдать результат как 0, он возвращает 5.

Также в интервью на хакерранке меня спросили: когда я попробовал этот подход, мне удалось решить только 4 тестовых случая из 15.

Каков правильный подход к решению этой проблемы.