Submission #230431

---

Source Code Expand

import java.io.IOException;
import java.util.ArrayList;

public class Main {
	static ArrayList<Integer> G[];
	
	static int T[];
	static int L[];
	static int D[];
	
	static int cnt;
	static void rec(int p, int v, int d) {
		int low = cnt;
		for(int w: G[v]) {
			if(w == p)
				continue;
			rec(v, w, d+1);
		}
		T[v] = cnt;
		L[cnt] = low;
		D[cnt] = d;
		cnt++;
	}
	
	public static void main(String[] args) {
		int N = nextInt();
		G = new ArrayList[N];
		for(int i = 0; i < N; i++) {
			G[i] = new ArrayList<Integer>();
		}
		for(int i = 0; i < N-1; i++) {
			int a = nextInt()-1;
			int b = nextInt()-1;
			G[a].add(b);
			G[b].add(a);
		}
		T = new int[N];
		L = new int[N];
		D = new int[N];
		rec(-1, 0, 0);
		int Q = nextInt();
		for(int i = 0; i < Q; i++) {
			int a = T[nextInt()-1];
			int b = T[nextInt()-1];
			
			if(a > b) {
				int tmp = a;
				a = b;
				b = tmp;
			}
			
			int low = b-1;
			int high = N-1;
			
			while(high - low > 1) {
				int m = (high+low)/2;
				
				if(b < L[m]) {
					low = m;
				} else if(L[m] <= a && b <= m) {
					high = m;
				} else {
					low = m;
				}
			}
			System.out.println(D[a] + D[b] - 2*D[high] + 1);
		}
	}
	
	static int nextInt() {
		int c;
		try {
			c = System.in.read();
			while(c != '-' && (c < '0' || c > '9')) c = System.in.read();
			if(c == '-') return -nextInt();
			int res = 0;
			while(c >= '0' && c <= '9') {
				res = res * 10 + c - '0';
				c = System.in.read();
			}
			return res;
		} catch (IOException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		}
		return -1;
	}
}

Submission Info

Compile Error

Note: ./Main.java uses unchecked or unsafe operations.
Note: Recompile with -Xlint:unchecked for details.

Judge Result