fork download
copy 
  1. import java.io.*;
  2. import java.util.ArrayList;
  3. import java.util.Arrays;
  4. import java.util.List;
  5. import java.util.Scanner;
  6. import java.util.StringTokenizer;
  7.  
  8. /*
  9.  Crafted on: 16/06/20
  10. */
  11. public class Main {
  12.     static int MAX_NODES = (int) 2e5;
  13.     static int MAX_DEPTH = 20;
  14.     static int[] depth = new int[MAX_NODES];
  15.     static long[] maxDownPath = new long[MAX_NODES];
  16.     static long[] maxUpPath = new long[MAX_NODES];
  17.  
  18.     static int[][] ances = new int[MAX_DEPTH][MAX_DEPTH];
  19.  
  20.     public class Edge {
  21.         int next;
  22.         long weight;
  23.  
  24.         public Edge(int next, long weight){
  25.             this.next = next;
  26.             this.weight = weight;
  27.         }
  28.     }
  29.  
  30.     private final int              n;
  31.     private final Scanner          reader;
  32.     private final List<List<Edge>> tree;
  33.     public Main(int n, Scanner reader) throws IOException {
  34.         this.n = n;
  35.         this.reader = reader;
  36.         this.tree = new ArrayList<>();
  37.  
  38.         for (int i = 0; i < n; i++) {
  39.             tree.add(new ArrayList<>());
  40.             Arrays.fill(ances[i], -1);
  41.         }
  42.         depth[0] = 0;
  43.         readTree();
  44.         dfs(0, -1, 0);
  45.  
  46.         for(int k=1; k<MAX_DEPTH ; k++)
  47.             for(int i=0;i<n; i++){
  48.                 int nextNode = ances[k-1][i];
  49.                 if(nextNode != -1)
  50.                     ances[k][i] = ances[k-1][nextNode];
  51.             }
  52.     }
  53.  
  54.     public int walk(int node, int k){
  55.         for(int i=0; i<MAX_DEPTH; i++)
  56.             if((1<<i & k) >0)
  57.                 node = ances[i][node];
  58.         return node;
  59.     }
  60.     public int findLCA(int u, int v){
  61.         if(depth[u] < depth[v])
  62.             v = walk(v, depth[v] -depth[v]);
  63.         if(depth[v] < depth[u])
  64.             u = walk(u, depth[u] - depth[v]);
  65.         if(u==v)
  66.             return u;
  67.         for(int i=MAX_DEPTH-1; i>=0 && (u != v); i--){
  68.             if(ances[i][u] != ances[i][v]) {
  69.                 u = ances[i][u];
  70.                 v = ances[i][v];
  71.             }
  72.         }
  73.         return ances[0][u];
  74.     }
  75.  
  76.     public long maxPath(int u, int v, long weight){
  77.         long ans = maxDownPath[u] + maxDownPath[v] + weight;
  78.         int ance = findLCA(u, v);
  79.         return Math.max(ans, maxUpPath[u] + maxUpPath[v] - 2*maxUpPath[ance]);
  80.     }
  81.  
  82.     public void readTree() throws IOException {
  83.         for(int i=0; i < n-1; i++) {
  84.             int u = reader.nextInt();
  85.             int v = reader.nextInt();
  86.             long weight = reader.nextLong();
  87.             tree.get(u - 1).add(new Edge(v - 1, weight));
  88.             tree.get(v - 1).add(new Edge(u - 1, weight));
  89.         }
  90.     }
  91.  
  92.     public void dfs(int node, int parent, long pathWeight){
  93.         long maxWght = 0;
  94.         maxUpPath[node] = pathWeight;
  95.       for(Edge edge: tree.get(node)){
  96.           if(edge.next != parent){
  97.               depth[edge.next] = depth[node] + 1;
  98.               ances[0][edge.next] = node;
  99.               dfs(edge.next,  node, pathWeight + edge.weight);
  100.               maxWght = Math.max(maxWght,  maxDownPath[edge.next]+ edge.weight);
  101.               maxWght = Math.max(maxWght, edge.weight);
  102.           }
  103.       }
  104.  
  105.       maxDownPath[node] = maxWght;
  106.  
  107.     }
  108.  
  109.     public static void main(String args[]) throws IOException {
  110.         Scanner reader = new Scanner(System.in);
  111.         // CODE GOES HERE
  112.  
  113.         int t = reader.nextInt();
  114.         while(t-- > 0){
  115.             int n = reader.nextInt();
  116.             int q = reader.nextInt();
  117.             Main main = new Main(n, reader);
  118.             while(q-- >0){
  119.                 int u = reader.nextInt();
  120.                 int v = reader.nextInt();
  121.                 long wt = reader.nextLong();
  122.                 writer.write(String.valueOf(main.maxPath(u-1, v-1, wt)));
  123.                 writer.newLine();
  124.             }
  125.         }
  126.  
  127.         writer.flush();
  128.         writer.close();
  129.     }
  130.  
  131.     static BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));
  132. }
Success #stdin #stdout 0.11s 39236KB
comments (?)
stdin
copy 
1
7 3
1 2 1
1 3 -2
2 4 3
2 5 -4
5 7 5
3 6 6
2 3 1
5 4 2
5 6 0
stdout
copy 
10
7
5
https://ideone.com/1GBGZh
language:
Java (HotSpot 12)
created:
3 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!