HackerEarth Diverging Directions problem solution

In this HackerEarth Diverging Directions problem solution You are given a directed weighted graph with n nodes and 2n – 2 edges. The nodes are labeled from 1 to n, while the edges are labeled from 1 to 2n – 2. The graph’s edges can be split into two parts.

• The first n – 1 edges will form a rooted spanning tree, with node 1 as the root. All these edges will point away from the root.
• The last n – 1 edges will be from node i to node 1, for all 2<=i<=n.

You are given q queries. There are two types of queries

• 1iw: Change the weight of the i-th edge to w
• 2uv: Print the length of the shortest path from node u to v

Given these queries, print the shortest path lengths.

import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.util.Arrays;
import java.io.BufferedWriter;
import java.util.InputMismatchException;
import java.io.IOException;
import java.util.ArrayList;
import java.util.List;
import java.util.stream.Stream;
import java.io.Writer;
import java.io.OutputStreamWriter;
import java.io.InputStream;

public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        InputReader in = new InputReader(inputStream);
        OutputWriter out = new OutputWriter(outputStream);
        DivergingDirections solver = new DivergingDirections();
        solver.solve(1, in, out);
        out.close();
    }

    static class DivergingDirections {
        public List<DivergingDirections.Edge>[] graph;
        public int[] tree_weight;
        public int[] star_weight;
        public int[] star_inv_weight;
        public int[] tree_perm;
        public int[] star_perm;
        public int[] start;
        public int[] end;
        public int tidx;
        public SegmentTreeFast root;

        public void dfs(int node, int par) {
            start[node] = tidx++;

            for (DivergingDirections.Edge e : graph[node]) {
                int next = e.to;
                if (next == par) continue;
                tree_perm[e.idx] = next;
                dfs(next, node);
            }
            end[node] = tidx - 1;
        }

        public int getDepth(int node) {
            return root.query(start[node], start[node]) - star_inv_weight[node];
        }

        public void solve(int testNumber, InputReader in, OutputWriter out) {
            int n = in.nextInt(), q = in.nextInt();
            graph = LUtils.genArrayList(n);
            tree_weight = new int[n];
            star_weight = new int[n];
            star_inv_weight = new int[n];
            tree_perm = new int[n];
            star_perm = new int[n];

            for (int i = 1; i <= n - 1; i++) {
                int a = in.nextInt() - 1, b = in.nextInt() - 1, c = in.nextInt();
                graph[a].add(new DivergingDirections.Edge(b, i));
                graph[b].add(new DivergingDirections.Edge(a, i));
                tree_weight[i] = c;
            }

            for (int i = n; i <= 2 * n - 2; i++) {
                int a = in.nextInt() - 1, b = in.nextInt() - 1, c = in.nextInt();
                star_weight[i - n + 1] = c;
                star_perm[i - n + 1] = a;
                star_inv_weight[a] = c;
            }
            start = new int[n];
            end = new int[n];
            dfs(0, -1);

            root = new SegmentTreeFast(tidx);
            for (int i = 1; i < n; i++) {
                int node = tree_perm[i];
                root.modify(start[node], end[node], tree_weight[i]);
            }
            for (int i = 1; i < n; i++) {
                int node = star_perm[i];
                root.modify(start[node], start[node], star_weight[i]);
            }

            while (q-- > 0) {
                int type = in.nextInt();
                if (type == 1) {
                    int edge = in.nextInt();
                    int new_weight = in.nextInt();
                    if (edge <= n - 1) {
                        int node = tree_perm[edge];
                        root.modify(start[node], end[node], new_weight - tree_weight[edge]);
                        tree_weight[edge] = new_weight;
                    } else {
                        edge -= n - 1;
                        int node = star_perm[edge];
                        root.modify(start[node], start[node], new_weight - star_weight[edge]);
                        star_weight[edge] = new_weight;
                        star_inv_weight[node] = new_weight;
                    }

                } else {
                    int a = in.nextInt() - 1, b = in.nextInt() - 1;

                    int ret = getDepth(b) - getDepth(a);
                    if (!(start[a] <= start[b] && end[b] <= end[a])) {
                        ret += root.query(start[a], end[a]);
                    }
                    out.println(ret);
                }
            }
        }

        static class Edge {
            public int to;
            public int idx;

            public Edge(int to, int idx) {
                this.to = to;
                this.idx = idx;
            }

        }

    }

    static class InputReader {
        private InputStream stream;
        private byte[] buf = new byte[1024];
        private int curChar;
        private int numChars;

        public InputReader(InputStream stream) {
            this.stream = stream;
        }

        public int read() {
            if (this.numChars == -1) {
                throw new InputMismatchException();
            } else {
                if (this.curChar >= this.numChars) {
                    this.curChar = 0;

                    try {
                        this.numChars = this.stream.read(this.buf);
                    } catch (IOException var2) {
                        throw new InputMismatchException();
                    }

                    if (this.numChars <= 0) {
                        return -1;
                    }
                }

                return this.buf[this.curChar++];
            }
        }

        public int nextInt() {
            int c;
            for (c = this.read(); isSpaceChar(c); c = this.read()) {
                ;
            }

            byte sgn = 1;
            if (c == 45) {
                sgn = -1;
                c = this.read();
            }

            int res = 0;

            while (c >= 48 && c <= 57) {
                res *= 10;
                res += c - 48;
                c = this.read();
                if (isSpaceChar(c)) {
                    return res * sgn;
                }
            }

            throw new InputMismatchException();
        }

        public static boolean isSpaceChar(int c) {
            return c == 32 || c == 10 || c == 13 || c == 9 || c == -1;
        }

    }

    static class SegmentTreeFast {
        int[] value;
        int[] delta;

        public SegmentTreeFast(int n) {
            value = new int[2 * n];
            for (int i = 0; i < n; i++) {
                value[i + n] = getInitValue();
            }
            for (int i = 2 * n - 1; i > 1; i -= 2) {
                value[i >> 1] = queryOperation(value[i], value[i ^ 1]);
            }
            delta = new int[2 * n];
            Arrays.fill(delta, getNeutralDelta());
        }

        int modifyOperation(int x, int y) {
            return x + y;
        }

        int queryOperation(int leftValue, int rightValue) {
            return Math.min(leftValue, rightValue);
        }

        int deltaEffectOnSegment(int delta, int segmentLength) {
            if (delta == getNeutralDelta()) return getNeutralDelta();
            // Here you must write a fast equivalent of following slow code:
            // int result = delta;
            // for (int i = 1; i < segmentLength; i++) result = queryOperation(result, delta);
            // return result;
            return delta;
        }

        int getNeutralDelta() {
            return (1 << 29);
        }

        int getInitValue() {
            return 0;
        }

        int joinValueWithDelta(int value, int delta) {
            if (delta == getNeutralDelta()) return value;
            return modifyOperation(value, delta);
        }

        int joinDeltas(int delta1, int delta2) {
            if (delta1 == getNeutralDelta()) return delta2;
            if (delta2 == getNeutralDelta()) return delta1;
            return modifyOperation(delta1, delta2);
        }

        void pushDelta(int i) {
            int d = 0;
            for (; (i >> d) > 0; d++) {
            }
            for (d -= 2; d >= 0; d--) {
                int x = i >> d;
                value[x >> 1] = joinNodeValueWithDelta(x >> 1, 1 << (d + 1));
                delta[x] = joinDeltas(delta[x], delta[x >> 1]);
                delta[x ^ 1] = joinDeltas(delta[x ^ 1], delta[x >> 1]);
                delta[x >> 1] = getNeutralDelta();
            }
        }

        int joinNodeValueWithDelta(int i, int len) {
            return joinValueWithDelta(value[i], deltaEffectOnSegment(delta[i], len));
        }

        public int query(int from, int to) {
            from += value.length >> 1;
            to += value.length >> 1;
            pushDelta(from);
            pushDelta(to);
            int res = 0;
            boolean found = false;
            for (int len = 1; from <= to; from = (from + 1) >> 1, to = (to - 1) >> 1, len <<= 1) {
                if ((from & 1) != 0) {
                    res = found ? queryOperation(res, joinNodeValueWithDelta(from, len)) : joinNodeValueWithDelta(from, len);
                    found = true;
                }
                if ((to & 1) == 0) {
                    res = found ? queryOperation(res, joinNodeValueWithDelta(to, len)) : joinNodeValueWithDelta(to, len);
                    found = true;
                }
            }
            if (!found) throw new RuntimeException();
            return res;
        }

        public void modify(int from, int to, int delta) {
            from += value.length >> 1;
            to += value.length >> 1;
            pushDelta(from);
            pushDelta(to);
            int a = from;
            int b = to;
            for (; from <= to; from = (from + 1) >> 1, to = (to - 1) >> 1) {
                if ((from & 1) != 0) {
                    this.delta[from] = joinDeltas(this.delta[from], delta);
                }
                if ((to & 1) == 0) {
                    this.delta[to] = joinDeltas(this.delta[to], delta);
                }
            }
            for (int i = a, len = 1; i > 1; i >>= 1, len <<= 1) {
                value[i >> 1] = queryOperation(joinNodeValueWithDelta(i, len), joinNodeValueWithDelta(i ^ 1, len));
            }
            for (int i = b, len = 1; i > 1; i >>= 1, len <<= 1) {
                value[i >> 1] = queryOperation(joinNodeValueWithDelta(i, len), joinNodeValueWithDelta(i ^ 1, len));
            }
        }

    }

    static class OutputWriter {
        private final PrintWriter writer;

        public OutputWriter(OutputStream outputStream) {
            writer = new PrintWriter(new BufferedWriter(new OutputStreamWriter(outputStream)));
        }

        public OutputWriter(Writer writer) {
            this.writer = new PrintWriter(writer);
        }

        public void close() {
            writer.close();
        }

        public void println(int i) {
            writer.println(i);
        }

    }

    static class LUtils {
        public static <E> List<E>[] genArrayList(int size) {
            return Stream.generate(ArrayList::new).limit(size).toArray(List[]::new);
        }

    }
}