Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- import java.io.IOException;
- import java.util.*;
- import java.io.*;
- public class rte16s3 {
- @SuppressWarnings("unchecked")
- static ArrayList<Integer>[] edges = new ArrayList[6005], weights = new ArrayList[6005];
- static int sparse[][] = new int[6005][15], depth[] = new int[6005];
- static long dist[][] = new long[6005][15];
- static void dfs(int node, int parent, int distance){
- sparse[node][0] = parent;
- dist[node][0] = distance;
- //update depth of node
- if (node == 0) depth[node] = 0;
- else depth[node] = depth[parent] + 1;
- //ancestor of 2^0 = 1 is parent
- for (int l = 1; l < 15; ++l){
- if (sparse[node][l - 1] == -1) sparse[node][l] = -1;
- else {
- //merge powers of two to form larger edges
- dist[node][l] = dist[node][l-1] + dist[sparse[node][l-1]][l-1];
- sparse[node][l] = sparse[sparse[node][l-1]][l-1];
- }
- }
- for(int l = 0; l < edges[node].size(); ++l){
- int next = edges[node].get(l);
- if (next == parent) continue; // dont go in a loop
- dfs(next, node, weights[node].get(l));
- }
- }
- static long query(int left, int right){
- long answer = 0;
- //make sure they are at the same depth
- int power = 14;
- while(depth[left] > depth[right]){
- //if the path doesnt exist, or it goes past the depth of right, decrease the power
- while(power > 0 && (sparse[left][power] == -1 || depth[sparse[left][power]] < depth[right])) power--;
- answer += dist[left][power];
- left = sparse[left][power];
- }
- while(depth[right] > depth[left]){
- //if the path doesnt exist, or it goes past the depth of right, decrease the power
- while(power > 0 && (sparse[right][power] == -1 || depth[sparse[right][power]] < depth[left])) power--;
- answer += dist[right][power];
- right = sparse[right][power];
- }
- //now they are on the same depth
- power = 14;
- while(left != right){
- while(power > 0 && (sparse[left][power] == -1 || sparse[left][power] == sparse[right][power])) power--;
- answer += dist[left][power];
- answer += dist[right][power];
- left = sparse[left][power];
- right = sparse[right][power];
- }
- return answer;
- }
- public static void main(String[] args) throws IOException{
- FastReader in = new FastReader(System.in);
- int n = in.nextInt();
- for (int l = 0; l < n; ++l){
- edges[l] = new ArrayList<Integer>();
- weights[l] = new ArrayList<Integer>();
- }
- for (int l = 0; l < n - 1; ++l){
- int a = in.nextInt(), b = in.nextInt(), w = in.nextInt();
- edges[a].add(b);
- weights[a].add(w);
- edges[b].add(a);
- weights[b].add(w);
- }
- dfs(0, -1, 0);
- int q = in.nextInt();
- for (int l = 0; l < q; ++l){
- int a = in.nextInt(), b = in.nextInt();
- System.out.println(query(a, b));
- }
- }
- static class FastReader
- {
- BufferedReader br;
- StringTokenizer st;
- public FastReader(InputStream x) {
- br = new BufferedReader(new
- InputStreamReader(x));
- }
- String next() {
- while (st == null || !st.hasMoreElements()) {
- try {
- st = new StringTokenizer(br.readLine());
- }
- catch (IOException e)
- {
- e.printStackTrace();
- }
- }
- return st.nextToken();
- }
- int nextInt()
- {
- return Integer.parseInt(next());
- }
- long nextLong()
- {
- return Long.parseLong(next());
- }
- double nextDouble()
- {
- return Double.parseDouble(next());
- }
- String nextLine()
- {
- String str = "";
- try
- {
- str = br.readLine();
- }
- catch (IOException e)
- {
- e.printStackTrace();
- }
- return str;
- }
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement