Submission #230432

---

Source Code Expand

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;

public class Main {

	public static void main(String[] args) {
		IO io = new IO();
		int n = io.nextInt();
		LCA lca = new LCA(n);
		for(int i=0;i<n-1;i++) {
			int x = io.nextInt()-1;
			int y = io.nextInt()-1;
			lca.addBidirectionalEdge(x, y);
		}
		lca.init();
		int q = io.nextInt();
		for(int i=0;i<q;i++) {
			int a = io.nextInt()-1;
			int b = io.nextInt()-1;
			io.println(lca.dist(a, b) + 1);
		}
		io.flush();
	}

}
class LCA {
	int n;
	ArrayList<Integer>[] tree;
	int[] map;
	RMQ<Node> rmq;
	@SuppressWarnings("unchecked")
	public LCA(int n) {
		this.n = n;
		tree = new ArrayList[n];
		for(int i=0;i<n;i++) {
			tree[i] = new ArrayList<>();
		}
	}
	public void addBidirectionalEdge(int u,int v) {
		tree[u].add(v);
		tree[v].add(u);
	}
	public void init() {
		map = new int[n];
		Arrays.fill(map, -1);
		rmq = new RMQ<Node>(2*n);
		dfs(-1,0,0,0);
	}
	private int dfs(int parent,int v,int count,int level) {
		rmq.update(count, new Node(count,level));
		if (map[v] < 0) {
			map[v] = count;
		}
		count++;
		for(int u:tree[v]) {
			if (u == parent) {
				continue;
			}
			count = dfs(v,u,count,level+1);
			rmq.update(count, new Node(count,level));
			count++;
		}
		return count;
	}
	public Node lca(int u,int v) {
		int u2 = map[u] < map[v] ? map[u] : map[v];
		int v2 = map[u] < map[v] ? map[v] : map[u];
		return rmq.query(u2, v2+1);
	}
	public int dist(int u,int v) {
		int a = rmq.get(map[u]).level;
		int b = rmq.get(map[v]).level;
		int c = lca(u,v).level;
		return Math.abs(a-c)+Math.abs(b-c);
	}
}
class Node implements Comparable<Node>{
	int id;
	int level;
	public Node(int id,int level) {
		this.id = id;
		this.level = level;
	}
	public int compareTo(Node o) {
		return Integer.compare(this.level, o.level);
	}
	public String toString() {
		return "(" + id + "," + level + ")";
	}
	
}
class RMQ<E extends Comparable<E>> {
	private int size;
	private int size_ = 1;
	private ArrayList<E> data;

	public RMQ(int size) {
		this.size = size;
		while(this.size_<this.size) {
			this.size_*=2;
		}
		data = new ArrayList<E>(Collections.nCopies(size_*2-1, (E) null));//[size_*2-1];
	}

	public E get(int k) {
		return data.get(k+size_-1);
	}

	public void update(int k,E a) {
		k+=size_-1;
		data.set(k, a);
		while(k>0) {
			k=(k-1)/2;
			data.set(k, min(data.get(k*2+1),data.get(k*2+2)));
		}
	}

	public E query(int a,int b) {
		return query(a,b,0,0,size_);
	}

	//[a,b)の区間について処理
	//kは接点の番号,[l,r)がkに対応する節点
	private E query(int a,int b,int k,int l,int r) {
		if (r<=a || b<=l) {
			return null;
		}
		if (a<=l && r<=b) {
			return data.get(k);
		}else{
			return min(query(a,b,k*2+1,l,(l+r)/2), query(a,b,k*2+2,(l+r)/2,r));
		}
	}

	//nullはINFとして扱う
	private E min(E a,E b) {
		if (a!=null && b!=null) {
			return a.compareTo(b)<0 ? a : b;
		}else if (a!=null) {
			return a;
		}else{
			return b;
		}
	}
	
	public String toString() {
		return data.subList(size_-1, size+size_).toString();
	}
}
class IO {
	BufferedReader bi = new BufferedReader(new InputStreamReader(System.in));
	StringBuilder out = new StringBuilder();
	int index = 0;
	String bfl = null;
	String[] bf = new String[0];
	private boolean read() {
		try {
			bfl = bi.readLine();
			if (bfl == null) {
				return false;
			}
			bf = bfl.split("\\s");
			index = 0;
		} catch (IOException e) {
			e.printStackTrace();
		}
		return true;
	}
	public boolean hasNext() { return index < bf.length ? true : read(); }
	public boolean hasNextLine() { return read(); }
	public String next() { return hasNext() ? bf[index++] : null; }
	public String nextLine() { return hasNextLine() ? bfl : null; }
	public int nextInt() { return Integer.parseInt(next()); }
	public long nextLong() { return Long.parseLong(next()); }
	public double nextDouble() { return Double.parseDouble(next()); };
	public void print(long x) { out.append(x); }
	public void print(double x) { out.append(x); }
	public void print(String s) { out.append(s); }
	public void println(long x) { out.append(x); out.append("\n"); }
	public void println(double x) { out.append(x); out.append("\n"); }
	public void println(String s) { out.append(s); out.append("\n"); }
	public void flush() {System.out.print(out); out = new StringBuilder(); }
	public int[] arrayInt(int n) {
		int[] a = new int[n];
		for(int i=0;i<n;i++) {
			a[i] = nextInt();
		}
		return a;
	}
	public long[] arrayLong(int n) {
		long[] a = new long[n];
		for(int i=0;i<n;i++) {
			a[i] = nextLong();
		}
		return a;
	}
	public double[] arrayDouble(int n) {
		double[] a = new double[n];
		for(int i=0;i<n;i++) {
			a[i] = nextDouble();
		}
		return a;
	}
}

Submission Info

Judge Result