fork download 
  1. import java.util.ArrayList;
  2. import java.util.Scanner;
  3. import static java.lang.Math.*;
  4.  
  5.  
  6. public class Main {
  7.     //problem specific variables
  8.     static ArrayList<Pair> adj[];
  9.     static int U[], V[];
  10.  
  11.     //HLD stuff
  12.     static int subtree_size[], chain[], chainHead[], position[], chainId = 0,pos = 0;
  13.  
  14.     //LCA stuff
  15.     static int parent[][], level[], MAX;
  16.  
  17.     //Segment tree related stuff
  18.     static int n, arr[], tree[];
  19.  
  20.     public static void main(String[] args) {
  21.         Scanner scanner = new Scanner(System.in);
  22.         int t = scanner.nextInt();
  23.         while(t-->0) {
  24.             //reset
  25.             chainId = 0;
  26.             pos = 0;
  27.  
  28.             n = scanner.nextInt();
  29.             MAX = (int)(log(n)/log(2));
  30.             adj = new ArrayList[n+1];
  31.             for(int i=1;i<=n;++i) {
  32.                 adj[i] = new ArrayList<>();
  33.             }
  34.             U = new int[n];
  35.             V = new int[n];
  36.             for(int i=1;i<n;++i) {
  37.                 int u = scanner.nextInt(), v = scanner.nextInt(), c = scanner.nextInt();
  38.                 adj[u].add(new Pair(v, c));
  39.                 adj[v].add(new Pair(u, c));
  40.                 U[i] = u;
  41.                 V[i] = v;
  42.             }
  43.             parent = new int[n+1][MAX+1];
  44.             chain = new int[n+1];
  45.             chainHead = new int[n+1];
  46.             position = new int[n+1];
  47.             subtree_size = new int[n+1];
  48.             arr = new int[n];
  49.             level = new int[n+1];
  50.             int sz = (int)pow(2, ceil(log(n)/log(2)) + 1);
  51.             tree = new int[sz];
  52.             dfs(1,0, 0);
  53.             chainHead[0] = 1;
  54.             HLD(1,0);
  55.             //print the array
  56.             build(1,0, n-1);
  57.             while(true) {
  58.                 String s = scanner.next();
  59.                 if(s.equals("DONE")) {
  60.                     break;
  61.                 }
  62.                 if(s.equals("QUERY")) {
  63.                     int u = scanner.nextInt(), v = scanner.nextInt() , LCA = lca(u,v);
  64.                     int max = 0;
  65.                     max = max(max, queryUp(u, LCA));
  66.                     max = max(max, queryUp(v, LCA));
  67.                     System.out.println(max);
  68.                 }
  69.                 else {
  70.                     int idx = scanner.nextInt(), cost = scanner.nextInt();
  71.                     int u = U[idx], v = V[idx];
  72.                     if(level[u]>level[v]) {
  73.                         update(position[u], cost);
  74.                     }
  75.                     else {
  76.                         update(position[v], cost);
  77.                     }
  78.                 }
  79.             }
  80.         }
  81.     }
  82.     static void dfs(int v, int par, int l) {
  83.         parent[v][0] = par;
  84.         for(int i=1;i<=MAX;++i) {
  85.             if(parent[v][i-1]!=0) {
  86.                 parent[v][i] = parent[parent[v][i-1]][i-1];
  87.             }
  88.         }
  89.         subtree_size[v] += 1;
  90.         level[v] = l;
  91.         for(Pair p : adj[v]) {
  92.             if(p.x!=par) {
  93.                 dfs(p.x, v, l+1);
  94.                 subtree_size[v]+=subtree_size[p.x];
  95.             }
  96.         }
  97.     }
  98.  
  99.      /**
  100.       * Decompose the tree into chains, keeping all of all values we need
  101.     */
  102.     static void HLD(int v, int par) {
  103.         int heavyChild = -1, heavySize = 0,heavyEdgeWeight = -1;
  104.         chain[v] = chainId;
  105.         position[v] = pos++;
  106.         for(Pair p : adj[v]) {
  107.             if(p.x!=par) {
  108.                 if(subtree_size[p.x] > heavySize) {
  109.                     heavySize = subtree_size[p.x];
  110.                     heavyChild = p.x;
  111.                     heavyEdgeWeight = p.y;
  112.                 }
  113.             }
  114.         }
  115.         if(heavyChild!=-1) {
  116.             arr[pos] = heavyEdgeWeight;
  117.             HLD(heavyChild, v);
  118.         }
  119.         for(Pair p : adj[v]) {
  120.             if(p.x != par && p.x != heavyChild) {
  121.                 chainId++;
  122.                 chainHead[chainId] = p.x;
  123.                 arr[pos] = p.y;
  124.                 HLD(p.x, v);
  125.             }
  126.         }
  127.     }
  128.  
  129.     /**
  130.      * Returns the maximum in path from node from to node to. Node to should be a ancestor of from.
  131.      * Uses the decomposition to reduce the number of queries to  at most log(n)
  132.      * @param from
  133.      * @param to
  134.      * @return
  135.      */
  136.     static int queryUp(int from, int to) {
  137.         int curr = from;
  138.         int ans = 0;
  139.         while(chain[curr] != chain[to]) {
  140.             ans = max(ans, query(position[chainHead[chain[curr]]], position[curr]));
  141.             curr = parent[chainHead[chain[curr]]][0];
  142.         }
  143.         ans = max(ans, query(position[to] + 1, position[curr]));
  144.         return ans;
  145.     }
  146.  
  147.     //calculates lca of node u and node v
  148.     static int lca(int u, int v) {
  149.         if(level[u]>level[v]) {
  150.             int temp = u;
  151.             u = v;
  152.             v = temp;
  153.         }
  154.         int diff = level[v] - level[u];
  155.         for(int i=MAX;i>=0;--i) {
  156.             if((diff&(1<<i))!=0) {
  157.                 v = parent[v][i];
  158.             }
  159.         }
  160.         if(u==v) {
  161.             return u;
  162.         }
  163.         for(int i=MAX;i>=0;--i) {
  164.             if(parent[u][i] != parent[v][i]) {
  165.                 u = parent[u][i];
  166.                 v = parent[v][i];
  167.             }
  168.         }
  169.         return parent[u][0];
  170.     }
  171.  
  172.     //segment tree build
  173.     static void build(int treein,int low,int high)
  174.     {
  175.         if(low==high)
  176.             tree[treein] = arr[low];
  177.         else
  178.         {
  179.             int mid = (low+high)>>1;
  180.             build(2*treein,low,mid);
  181.             build(2*treein+1,mid+1,high);
  182.             tree[treein] = max(tree[2*treein],tree[2*treein+1]);
  183.         }
  184.     }
  185.     //segment tree update
  186.     static void update(int treein,int low,int high,int idx,int val)
  187.     {
  188.         if(low==high)
  189.             tree[treein] = val;
  190.         else
  191.         {
  192.             int mid = (low+high)>>1;
  193.             if(idx<=mid)
  194.                 update(2*treein,low,mid,idx,val);
  195.             else update(2*treein+1,mid+1,high,idx,val);
  196.             tree[treein] = max(tree[2*treein],tree[2*treein+1]);
  197.         }
  198.     }
  199.     //segment tree query
  200.     static int query(int treein,int low,int high,int l,int r)
  201.     {
  202.         if(l<=low && high<=r)
  203.             return tree[treein];
  204.         if(low>r || high<l)
  205.             return 0;
  206.         int mid = (low+high)>>1;
  207.         return max(query(2*treein,low,mid,l,r),query(2*treein+1,mid+1,high,l,r));
  208.     }
  209.     static int query(int l,int r)
  210.     {
  211.         if(l>r) {
  212.             return 0;
  213.         }
  214.         return query(1,0,n-1,l,r);
  215.     }
  216.     static void update(int idx,int val)
  217.     {
  218.         update(1,0,n-1,idx,val);
  219.     }
  220.     static class Pair implements Comparable<Pair>
  221.     {
  222.         int x,y;
  223.         Pair(int x,int y)
  224.         {
  225.             this.x=x;
  226.             this.y=y;
  227.         }
  228.         public int compareTo(Pair other)
  229.         {
  230.             if(this.x!=other.x)
  231.                 return this.x-other.x;
  232.             return this.y-other.y;
  233.         }
  234.         public String toString()
  235.         {
  236.             return "("+x+","+y+")";
  237.         }
  238.     }
  239. }
  240. /*
  241. 2
  242.  
  243. 3
  244. 1 2 1
  245. 1 3 2
  246. QUERY 1 2
  247. CHANGE 1 3
  248. QUERY 1 2
  249. DONE
  250.  
  251. 3
  252. 1 2 1
  253. 1 3 2
  254. QUERY 1 2
  255. CHANGE 1 3
  256. QUERY 1 2
  257. DONE
  258.  */
Success #stdin #stdout 0.13s 56280KB
comments (?)
stdin 
1
3
1 2 1
1 3 2
QUERY 1 2
CHANGE 1 3
QUERY 1 2
DONE
stdout 
1
3
https://ideone.com/DntOVr
language:
Java (HotSpot 12)
created:
5 days 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!