CareerCup

Segment tree could be one possible solution but don't know how to change this problem in Segment tree, any suggestions?

bfs find shortest path between two nodes

public static void main(String[] args) {
		// TODO Auto-generated method stub
       Scanner sc = new Scanner (System.in);
       int n = sc.nextInt() ;
       int m = sc.nextInt() ;
       int i = 0 ;
       int [][] data = new int [n - 1][2] ;
       while (i < n - 1) {
    	   data[i][0] = sc.nextInt() ;
    	   data[i][1] = sc.nextInt() ;
    	   i++;
       }
       i = 0 ;
       int [][] query = new int [m][2] ;
       while (i < m) {
    	   query[i][0] = sc.nextInt() ;
    	   query[i][1] = sc.nextInt() ;
    	   i++;
       }
       getPath(data, query, n);
	}

	
	public static HashMap<Integer,List<Integer>> createGraph (int n, int [][] ar){
		HashMap<Integer,List<Integer>> graph = new HashMap<> ();
		for (int i = 1 ; i <= n ; ++i) {
			graph.put(i, new ArrayList<Integer>());
		}		
		for (int [] a : ar) {
			graph.get(a[0]).add(a[1]) ;
			graph.get(a[1]).add(a[0]) ;
		}		
		return graph ;
	}
	
	public static void getPath (int [][] ar, int [][] query,int n){
		HashMap<Integer,List<Integer>> graph = createGraph (n ,ar);
	
		HashMap<Integer,Boolean> city = new HashMap<> ();
		city.put(1, true) ;		
		for (int [] a : query) {
			if (a[0] == 1) {				
				city.put(a[1], true) ;
			} else {				
				bfs (graph,city, a[1]);
			}
		}
	}
	
	public static void bfs (HashMap<Integer,List<Integer>> graph, HashMap<Integer,Boolean> city , int start){
		HashMap<Integer,Integer> visited = new HashMap<> ();	
		Queue<Integer> q = new LinkedList<> () ;
		visited.put(start, 0) ;
		q.offer(start) ;
		while (!q.isEmpty()) {			
			int cur = q.poll() ;
			if (city.containsKey(cur)) {
				System.out.println(visited.get(cur));
				break;
			}
			for (int n : graph.get(cur)) {
				if (!visited.containsKey(n)) {
					visited.put(n, visited.get(cur) + 1) ;
					q.add(n) ;
				}
			}
		}
	}

Each city could be a node and every node has a list of neighbor node(so it become a tree-like structure and every node could be the root), this is a easy approach when n is not big(as in the problem it is less than 105)

Guys sorry for the wrong info n and m are ranging from 2 to 10^5 and 1 to 10^5 respectively.