BOJ. Tree and Query 2 (13511)

import java.util.*;
import java.io.*;

public class Main {
	static BufferedReader br;
	static StringBuilder sb = new StringBuilder();
	static int log, n;
	static long[][] costArr;
	static int[][] parent;
	static Node[] nodes;
	public static void main(String[] args) throws IOException {
		br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		n = toi(br.readLine());
		log = (int)(Math.log(n) / Math.log(2)) + 1;
		nodes = new Node[n];
		for(int i = 0; i < n; i++) nodes[i] = new Node(i);
		int[] arr;

		for(int i = 0; i < n - 1; i++) {
			arr = getArr();
			int a = arr[0] - 1, b = arr[1] - 1, cost = arr[2];
			nodes[a].list.add(new Edge(nodes[b], cost));
			nodes[b].list.add(new Edge(nodes[a], cost));
		}

		costArr = new long[n][log + 1];
		parent = new int[n][log + 1];
		for(long[] ar: costArr)Arrays.fill(ar, -1);
		for(int[] ar: parent)Arrays.fill(ar, -1);

		initSparseDFS(nodes[0]);

		fillSparseParent();
		fillSparseCost();

		int m = toi(br.readLine());

		for(int i = 0; i < m; i++) {
			arr = getArr();
			int a = arr[1] - 1, b = arr[2] - 1;
			if(arr[0] == 1) { // costArr from a to b
				sb.append(getCost(a, b)).append("\n");
			} else { // in path a~b : k th point
				sb.append(getKthVertext(a, b, arr[3]) + 1).append("\n");
			}
		}

		print(sb);
	}

	static long getCost(int a, int b) {
		long cost = 0l;

		if(nodes[a].depth < nodes[b].depth) {
			int tmp = a;
			a = b;
			b = tmp;
		}

		for(int i = log; i >= 0; i--)
			if(nodes[a].depth - nodes[b].depth >= 1 << i) {
				cost += costArr[a][i];
				a = parent[a][i];
			}

		if(a == b) return cost;

		for(int i = log; i >= 0; i--) {
			if(parent[a][i] != parent[b][i]) {
				cost += (costArr[a][i] + costArr[b][i]);
				a = parent[a][i];
				b = parent[b][i];
			}
		}
		return cost + costArr[a][0] + costArr[b][0];
	}

	static int getKthVertext(int a, int b, int targetIdx) {
		int nth = 1;
		boolean swapped = false;

		if(nodes[a].depth < nodes[b].depth) {
			int tmp = a;
			a = b;
			b = tmp;
			swapped = true;
		}

		int origB = b, origA = a;

		for(int i = log; i >= 0; i--)
			if(nodes[a].depth - nodes[b].depth >= 1 << i) {
				nth += (1 << i);
				a = parent[a][i];
			}

		int elavateCnt = 0;

		if(a != b) {
			for(int i = log; i >= 0; i--) {
				if(parent[a][i] != parent[b][i]) {
					a = parent[a][i];
					b = parent[b][i];
					elavateCnt += (1 << i);
				}
			}
			elavateCnt++;
		}

		int totalLen = nth + 2 * elavateCnt;
		if(swapped) targetIdx = totalLen + 1 - targetIdx;

		if(nth + elavateCnt >= targetIdx) {
			nth = 1;
			for(int i = log; i >= 0; i--) {
				if(targetIdx - nth >= 1 << i) {
					nth += (1 << i);
					origA = parent[origA][i];
				}
			}
			return nodes[origA].idx;
		}

		// From nth + elavateCnt => 2 * elavateCnt + nth, targetIdx =>
		targetIdx = totalLen + 1 - targetIdx;
		nth = 1;
		for(int i = log; i >= 0; i--) {
			if(targetIdx - nth >= 1 << i) {
				nth += (1 << i);
				origB = parent[origB][i];
			}
		}

		return nodes[origB].idx;
	}

	static void initSparseDFS(Node node) {
		for(Edge edge: node.list) {
			if(node.parent == edge.to.idx) continue;
			edge.to.parent = node.idx;
			parent[edge.to.idx][0] = node.idx;
			costArr[edge.to.idx][0] = (long)edge.cost;
			edge.to.depth = node.depth + 1;
			initSparseDFS(edge.to);
		}
	}

	static void fillSparseParent() {
		for(int j = 1; j <= log; j++) {
			for(int i = 0; i < n; i++) {
				if(parent[i][j - 1] != -1)
					parent[i][j] = parent[parent[i][j - 1]][j - 1];
			}
		}
	}

	static void fillSparseCost() {
		for(int j = 1; j <= log; j++) {
			for(int i = 0; i < n; i++) {
				if(parent[i][j] != - 1)
					costArr[i][j] = costArr[i][j - 1] + costArr[parent[i][j - 1]][j - 1];
			}
		}
	}

	static class Node {
		int idx;
		int parent = -1;
		int depth = 0;
		ArrayList<Edge> list = new ArrayList<>();
		public Node(int idx) { this.idx = idx; }
	}

	static class Edge {
		Node to;
		int cost;
		public Edge(Node to, int cost) { this.to = to; this.cost = cost; }
	}

	static int toi(String s) { return Integer.parseInt(s); }
	static String[] getLine() throws IOException { return br.readLine().split(" "); }
	static int[] getArr() throws IOException { return Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray(); }
	static <T> void print(T s) { System.out.print(s); }
	static <T> void println(T s) { System.out.println(s); }
}