Advertisement
Guest User

Untitled

a guest
Oct 19th, 2019
97
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 4.34 KB | None | 0 0
  1. import java.io.IOException;
  2. import java.util.*;
  3. import java.io.*;
  4. public class rte16s3 {
  5. @SuppressWarnings("unchecked")
  6. static ArrayList<Integer>[] edges = new ArrayList[6005], weights = new ArrayList[6005];
  7. static int sparse[][] = new int[6005][15], depth[] = new int[6005];
  8. static long dist[][] = new long[6005][15];
  9. static void dfs(int node, int parent, int distance){
  10. sparse[node][0] = parent;
  11. dist[node][0] = distance;
  12. //update depth of node
  13. if (node == 0) depth[node] = 0;
  14. else depth[node] = depth[parent] + 1;
  15. //ancestor of 2^0 = 1 is parent
  16. for (int l = 1; l < 15; ++l){
  17. if (sparse[node][l - 1] == -1) sparse[node][l] = -1;
  18. else {
  19. //merge powers of two to form larger edges
  20. dist[node][l] = dist[node][l-1] + dist[sparse[node][l-1]][l-1];
  21. sparse[node][l] = sparse[sparse[node][l-1]][l-1];
  22. }
  23. }
  24. for(int l = 0; l < edges[node].size(); ++l){
  25. int next = edges[node].get(l);
  26. if (next == parent) continue; // dont go in a loop
  27. dfs(next, node, weights[node].get(l));
  28. }
  29. }
  30. static long query(int left, int right){
  31. long answer = 0;
  32. //make sure they are at the same depth
  33. int power = 14;
  34. while(depth[left] > depth[right]){
  35. //if the path doesnt exist, or it goes past the depth of right, decrease the power
  36. while(power > 0 && (sparse[left][power] == -1 || depth[sparse[left][power]] < depth[right])) power--;
  37. answer += dist[left][power];
  38. left = sparse[left][power];
  39. }
  40. while(depth[right] > depth[left]){
  41. //if the path doesnt exist, or it goes past the depth of right, decrease the power
  42. while(power > 0 && (sparse[right][power] == -1 || depth[sparse[right][power]] < depth[left])) power--;
  43. answer += dist[right][power];
  44. right = sparse[right][power];
  45. }
  46. //now they are on the same depth
  47. power = 14;
  48. while(left != right){
  49. while(power > 0 && (sparse[left][power] == -1 || sparse[left][power] == sparse[right][power])) power--;
  50. answer += dist[left][power];
  51. answer += dist[right][power];
  52. left = sparse[left][power];
  53. right = sparse[right][power];
  54. }
  55. return answer;
  56. }
  57. public static void main(String[] args) throws IOException{
  58. FastReader in = new FastReader(System.in);
  59. int n = in.nextInt();
  60. for (int l = 0; l < n; ++l){
  61. edges[l] = new ArrayList<Integer>();
  62. weights[l] = new ArrayList<Integer>();
  63. }
  64. for (int l = 0; l < n - 1; ++l){
  65. int a = in.nextInt(), b = in.nextInt(), w = in.nextInt();
  66. edges[a].add(b);
  67. weights[a].add(w);
  68. edges[b].add(a);
  69. weights[b].add(w);
  70. }
  71. dfs(0, -1, 0);
  72. int q = in.nextInt();
  73. for (int l = 0; l < q; ++l){
  74. int a = in.nextInt(), b = in.nextInt();
  75. System.out.println(query(a, b));
  76. }
  77. }
  78. static class FastReader
  79. {
  80. BufferedReader br;
  81. StringTokenizer st;
  82. public FastReader(InputStream x) {
  83. br = new BufferedReader(new
  84. InputStreamReader(x));
  85.  
  86. }
  87.  
  88. String next() {
  89. while (st == null || !st.hasMoreElements()) {
  90. try {
  91. st = new StringTokenizer(br.readLine());
  92. }
  93. catch (IOException e)
  94. {
  95. e.printStackTrace();
  96. }
  97. }
  98. return st.nextToken();
  99. }
  100.  
  101. int nextInt()
  102. {
  103. return Integer.parseInt(next());
  104. }
  105.  
  106. long nextLong()
  107. {
  108. return Long.parseLong(next());
  109. }
  110.  
  111. double nextDouble()
  112. {
  113. return Double.parseDouble(next());
  114. }
  115.  
  116. String nextLine()
  117. {
  118. String str = "";
  119. try
  120. {
  121. str = br.readLine();
  122. }
  123. catch (IOException e)
  124. {
  125. e.printStackTrace();
  126. }
  127. return str;
  128. }
  129. }
  130.  
  131. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement