| 75 | } |
| 76 | |
| 77 | public static void compute() { |
| 78 | int ei = 1, queryId, unionCnt; |
| 79 | for (int l = 1, r = 1; l <= k; l = ++r) { |
| 80 | while (r + 1 <= k && queries[l][2] == queries[r + 1][2] && queries[l][3] == queries[r + 1][3]) { |
| 81 | r++; |
| 82 | } |
| 83 | // 添加小于当前边权的边，利用Kruskal算法增加连通性，ei是不回退的 |
| 84 | for (; ei <= m && edge[ei][2] < queries[l][2]; ei++) { |
| 85 | if (find(edge[ei][0]) != find(edge[ei][1])) { |
| 86 | union(edge[ei][0], edge[ei][1]); |
| 87 | } |
| 88 | } |
| 89 | queryId = queries[l][3]; |
| 90 | if (!ans[queryId]) { |
| 91 | continue; |
| 92 | } |
| 93 | unionCnt = 0; |
| 94 | for (int i = l; i <= r; i++) { |
| 95 | if (find(queries[i][0]) == find(queries[i][1])) { |
| 96 | ans[queryId] = false; |
| 97 | break; |
| 98 | } else { |
| 99 | union(queries[i][0], queries[i][1]); |
| 100 | unionCnt++; |
| 101 | } |
| 102 | } |
| 103 | for (int i = 1; i <= unionCnt; i++) { |
| 104 | undo(); |
| 105 | } |
| 106 | } |
| 107 | } |
| 108 | |
| 109 | public static void main(String[] args) throws IOException { |
| 110 | BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); |