# 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.

## HackerEarth Diverging Directions problem solution.

`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);        }    }}`