Find node U containing all nodes from a set V at atmost distance 1 from the path from root to U | Java program for the above approach ; To store the time ; Function to perform DFS to store times , distance and parent of each node ; Update the distance of node u ; Update parent of node u ; Increment time timeT ; Discovery time of node u ; Traverse the adjacency list of current node and recursively call DFS for each vertex ; If current node Adj [ u ] [ i ] is unvisited ; Update the finishing time ; Function to add edges between nodes u and v ; Function to find the node U such that path from root to U contains nodes in V [ ] ; Initialise vis , dis , parent , preTime , and postTime ; Store Adjacency List ; Create adjacency List ; Perform DFS Traversal ; Stores the distance of deepest vertex ' u ' ; Update the deepest node by traversing the qu [ ] ; Find deepest vertex ; Replace each vertex with it 's  corresponding parent except  the root vertex ; Checks if the ancestor with respect to deepest vertex u ; Update ans ; Print the result ; Driver Code ; Total vertices ; Given set of vertices ; Given edges ; Function call
import java . util . * ; class GFG { static int timeT = 0 ; static void dfs ( int u , int p , int dis , int vis [ ] , int distance [ ] , int parent [ ] , int preTime [ ] , int postTime [ ] , ArrayList < ArrayList < Integer > > Adj ) { distance [ u ] = dis ; parent [ u ] = p ; vis [ u ] = 1 ; timeT ++ ; preTime [ u ] = timeT ; for ( int i = 0 ; i < Adj . get ( u ) . size ( ) ; i ++ ) { if ( vis [ Adj . get ( u ) . get ( i ) ] == 0 ) { dfs ( Adj . get ( u ) . get ( i ) , u , dis + 1 , vis , distance , parent , preTime , postTime , Adj ) ; } } timeT ++ ; postTime [ u ] = timeT ; } static void addEdge ( ArrayList < ArrayList < Integer > > Adj , int u , int v ) { Adj . get ( u ) . add ( v ) ; Adj . get ( v ) . add ( u ) ; } static void findNodeU ( int N , int V , int Vertices [ ] , int Edges [ ] [ ] ) { int vis [ ] = new int [ N + 1 ] ; int distance [ ] = new int [ N + 1 ] ; int parent [ ] = new int [ N + 1 ] ; int preTime [ ] = new int [ N + 1 ] ; int postTime [ ] = new int [ N + 1 ] ; ArrayList < ArrayList < Integer > > Adj = new ArrayList < > ( ) ; for ( int i = 0 ; i < N + 1 ; i ++ ) Adj . add ( new ArrayList < Integer > ( ) ) ; int u = 0 , v ; for ( int i = 0 ; i < N - 1 ; i ++ ) { addEdge ( Adj , Edges [ i ] [ 0 ] , Edges [ i ] [ 1 ] ) ; } dfs ( 1 , 0 , 0 , vis , distance , parent , preTime , postTime , Adj ) ; int maximumDistance = 0 ; maximumDistance = 0 ; for ( int k = 0 ; k < V ; k ++ ) { if ( maximumDistance < distance [ Vertices [ k ] ] ) { maximumDistance = distance [ Vertices [ k ] ] ; u = Vertices [ k ] ; } if ( parent [ Vertices [ k ] ] != 0 ) { Vertices [ k ] = parent [ Vertices [ k ] ] ; } } boolean ans = true ; boolean flag ; for ( int k = 0 ; k < V ; k ++ ) { if ( preTime [ Vertices [ k ] ] <= preTime [ u ] && postTime [ Vertices [ k ] ] >= postTime [ u ] ) flag = true ; else flag = false ; ans = ans & flag ; } if ( ans ) System . out . println ( u ) ; else System . out . println ( " NO " ) ; } public static void main ( String [ ] args ) { int N = 10 ; int V = 5 ; int Vertices [ ] = { 4 , 3 , 8 , 9 , 10 } ; int Edges [ ] [ ] = { { 1 , 2 } , { 1 , 3 } , { 1 , 4 } , { 2 , 5 } , { 2 , 6 } , { 3 , 7 } , { 7 , 8 } , { 7 , 9 } , { 9 , 10 } } ; findNodeU ( N , V , Vertices , Edges ) ; } }