Graph / Tree / Bridges

import java.util.*;
import java.math.*;

import static java.lang.Math.*;

public class AqaAsadiSaves {

    class Edge {
        int to, id;

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

    }

    class SuperVertex {
        List<Integer> insideVertices;

        SuperVertex() {
            insideVertices = new ArrayList<>();
        }

        public void add(int v) {
            insideVertices.add(v);
        }

        @Override
        public String toString() {
            return "SuperVertex{" +
                    "insideVertices=" + insideVertices +
                    '}';
        }
    }

    class Dsu {
        int[] p;

        int get(int x) {
            return p[x] == x ? x : (p[x] = get(p[x]));
        }

        void unite(int x, int y) {
            p[get(x)] = get(y);
        }

        Dsu(int n) {
            p = new int[n];
            for (int i = 0; i < n; i++) {
                p[i] = i;
            }
        }
    }

    class TreeForest {
        List<Integer>[] g;
        int[] rootIds;
        int n;
        int time;
        int[] tin, tout;
        int layers;
        int[][] up;

        TreeForest(int n) {
            this.n = n;
            g = new List[n];
            for (int i = 0; i < n; i++) {
                g[i] = new ArrayList<>();
            }
            tin = new int[n];
            tout = new int[n];
        }

        void addEdge(int fr, int to) {
            g[fr].add(to);
            g[to].add(fr);
        }

        void dfs(int v, int rootId, int p) {
            up[0][v] = p;
            for (int i = 1; i < up.length; i++) {
                up[i][v] = up[i - 1][up[i - 1][v]];
            }
            tin[v] = time++;
            rootIds[v] = rootId;
            for (int to : g[v]) {
                if (to == p) {
                    continue;
                }
                dfs(to, rootId, v);
            }
            tout[v] = time;
        }

        boolean isInside(int parent, int ch) {
            return tin[ch] >= tin[parent] && tout[ch] <= tout[parent];
        }

        int lca(int x, int y) {
            for (int i = layers - 1; i >= 0; i--) {
                if (!isInside(up[i][x], y)) {
                    x = up[i][x];
                }
            }
            if (isInside(x, y)) {
                return x;
            }
            return up[0][x];
        }

        boolean isOnPath(int from, int to, int what) {
            int lca = lca(from, to);
            if (!isInside(lca, what)) {
                return false;
            }
            return isInside(what, from) || isInside(what, to);
        }

        void build() {
            // TODO: change 2?
            layers = Integer.numberOfTrailingZeros(Integer.highestOneBit(n)) + 2;
            up = new int[layers][n];
            rootIds = new int[n];
            Arrays.fill(rootIds, -1);
            for (int i = 0; i < n; i++) {
                if (rootIds[i] != -1) {
                    continue;
                }
                dfs(i, i, i);
            }
        }
    }

    class TwoConnectedComponents {
        SuperVertex[] vertices;
        List<Integer>[] graph;

        public TwoConnectedComponents(SuperVertex[] vertices, List<Integer>[] graph) {
            this.vertices = vertices;
            this.graph = graph;
        }

        @Override
        public String toString() {
            return "TwoConnectedComponents{" +
                    "vertices=" + Arrays.toString(vertices) +
                    ", graph=" + Arrays.toString(graph) +
                    '}';
        }
    }

    class Graph {
        int n;
        List<Edge>[] g;
        int totEdges;
        int[] tin, fup;
        int timer;


        Graph(int n) {
            this.n = n;
            g = new List[n];
            for (int i = 0; i < n; i++) {
                g[i] = new ArrayList<>();
            }
        }

        void addEdge(int fr, int to) {
            Edge e1 = new Edge(to, totEdges);
            Edge e2 = new Edge(fr, totEdges);
            g[fr].add(e1);
            g[to].add(e2);
            totEdges++;
        }

        void dfs(int v, int pEdgeId, boolean[] was, boolean[] isBridge) {
            was[v] = true;
            tin[v] = fup[v] = timer++;
            for (int i = 0; i < g[v].size(); i++) {
                Edge e = g[v].get(i);
                if (e.id == pEdgeId) {
                    continue;
                }
                if (was[e.to]) {
                    fup[v] = Math.min(fup[v], tin[e.to]);
                } else {
                    dfs(e.to, e.id, was, isBridge);
                    fup[v] = Math.min(fup[v], fup[e.to]);
                    if (fup[e.to] > tin[v]) {
                        isBridge[e.id] = true;
                    }
                }
            }
        }

        TwoConnectedComponents findTwoConnectedComponents() {
            boolean[] isBridge = new boolean[totEdges];
            boolean[] was = new boolean[n];
            tin = new int[n];
            fup = new int[n];
            for (int v = 0; v < n; v++) {
                if (was[v]) {
                    continue;
                }
                dfs(v, -1, was, isBridge);
            }
            Dsu dsu = new Dsu(n);
            for (int i = 0; i < n; i++) {
                for (Edge e : g[i]) {
                    if (isBridge[e.id]) {
                        continue;
                    }
                    dsu.unite(i, e.to);
                }
            }
            int[] newId = new int[n];
            Arrays.fill(newId, -1);
            int nSz = 0;
            for (int i = 0; i < n; i++) {
                int p = dsu.get(i);
                if (newId[p] == -1) {
                    newId[p] = nSz++;
                }
                newId[i] = newId[p];
            }
            SuperVertex[] vertices = new SuperVertex[nSz];
            for (int i = 0; i < vertices.length; i++) {
                vertices[i] = new SuperVertex();
            }
            for (int i = 0; i < n; i++) {
                vertices[newId[i]].add(i);
            }
            List<Integer>[] newGraph = new List[nSz];
            for (int i = 0; i < newGraph.length; i++) {
                newGraph[i] = new ArrayList<>();
            }
            for (int i = 0; i < n; i++) {
                for (Edge e : g[i]) {
                    if (isBridge[e.id]) {
                        newGraph[newId[i]].add(newId[e.to]);
                    }
                }
            }
            return new TwoConnectedComponents(vertices, newGraph);
        }
    }

    class WeightedEdge implements Comparable<WeightedEdge> {
        int fr, to;
        long cost;

        public WeightedEdge(int fr, int to, long cost) {
            this.fr = fr;
            this.to = to;
            this.cost = cost;
        }

        @Override
        public int compareTo(WeightedEdge o) {
            return -Long.compare(cost, o.cost);
        }

        @Override
        public String toString() {
            return "WeightedEdge{" +
                    "fr=" + fr +
                    ", to=" + to +
                    ", cost=" + cost +
                    '}';
        }
    }

    int findWeightedEdges(TreeForest treeForest, List<WeightedEdge> edges, int v, int p, TwoConnectedComponents twoConnectedComponents) {
        int sz = twoConnectedComponents.vertices[v].insideVertices.size();
        for (int to : treeForest.g[v]) {
            if (to == p) {
                continue;
            }
            int chSz = findWeightedEdges(treeForest, edges, to, v, twoConnectedComponents);
            edges.add(new WeightedEdge(v, to, chSz));
            sz += chSz;
        }
        return sz;
    }

    void addToPath(int[] path, int v, TreeForest treeForest) {
        if (path[0] == -1) {
            return;
        }
        if (treeForest.isOnPath(path[0], path[1], v)) {
            return;
        }
        if (treeForest.isOnPath(path[0], v, path[1])) {
            path[1] = v;
            return;
        }
        if (treeForest.isOnPath(v, path[1], path[0])) {
            path[0] = v;
            return;
        }
        path[0] = path[1] = -1;
    }

    public long minDamage(int N, int M, int[] PA, int[] PB, int Seed, int X, int Y) {
        int[] a = new int[M];
        int[] b = new int[M];
        for (int i = 0; i < M; i++) {
            if (i < PA.length) {
                a[i] = PA[i];
            } else {
                a[i] = Seed;
                Seed = (int) ((Seed * 1L * X + Y) % N);
            }
        }
        for (int i = 0; i < M; i++) {
            if (i < PB.length) {
                b[i] = PB[i];
            } else {
                b[i] = Seed;
                Seed = (int) ((Seed * 1L * X + Y) % N);
            }
        }
        Graph graph = new Graph(N);
        for (int i = 0; i < M; i++) {
            graph.addEdge(a[i], b[i]);
        }
        TwoConnectedComponents twoConnectedComponents = graph.findTwoConnectedComponents();
        int nSz = twoConnectedComponents.graph.length;
        TreeForest treeForest = new TreeForest(nSz);
        for (int v = 0; v < nSz; v++) {
            for (int to : twoConnectedComponents.graph[v]) {
                if (to < v) {
                    continue;
                }
                treeForest.addEdge(v, to);
            }
        }
        treeForest.build();
        List<WeightedEdge> allEdges = new ArrayList<>();
        for (int v = 0; v < nSz; v++) {
            if (treeForest.rootIds[v] != v) {
                continue;
            }
            List<WeightedEdge> edges = new ArrayList<>();
            int curSize = findWeightedEdges(treeForest, edges, v, v, twoConnectedComponents);
            for (WeightedEdge e : edges) {
                e.cost *= curSize - e.cost;
            }
            allEdges.addAll(edges);
        }
        Collections.sort(allEdges);
        int[] path = new int[]{-1, -1};
        for (WeightedEdge e : allEdges) {
            if (path[0] == -1) {
                path = new int[]{e.fr, e.to};
            } else {
                addToPath(path, e.fr, treeForest);
                addToPath(path, e.to, treeForest);
            }
            if (path[0] == -1) {
                return e.cost;
            }
        }
        return 0;
    }
}