My take for Q1. Assuming 1 <= A[i] (cost) <= 2^30
It is always more optimal to delete the higher bit, so what I did is that I delete the edges from the highest bit to the lowest bit.
If deleting a bit and the graph is still connected, then we remove ALL (cuz it is OR) the edges containing that bit.
I run UF (path compression + union by rank) each time for each deletion, so the time complexity is about O(30N).
It is 3AM here and I had a really long day. Did not bother to stress test my code, but it passed the sample test case.
As for the cycle thing, I think it doesn't matter, but it is really late and I am exhausted, so I will just leave this here for now.
Java
private static int solve(int N, int[][] edges){
BitSet byebye = new BitSet();
BitSet[] bit = new BitSet[31];
Arrays.setAll(bit, o -> new BitSet());
for (int i = 0; i < edges.length; i++){ // [from, to, cost]
edges[i][0]--; edges[i][1]--; // one index is so evil.
for (int cost = edges[i][2], pos = 0; cost > 0; cost>>=1, pos++){
if ((cost&1)>0){ // let's get the position first.
bit[pos].set(i);
}
}
}
for (int i = 30; i >= 0; i--){ // run deletion from highest bit to the lowest
BitSet ignore = (BitSet)byebye.clone();
ignore.or(bit[i]); // delete these all
UF uf = new UF(N);
for (int j = ignore.nextClearBit(0); j < N; j = ignore.nextClearBit(j+1)){
uf.union(edges[j][0], edges[j][1]); // union the remaining edges
}
if (uf.sz == 1){ // if still all connected, then update byebye to ignore.
byebye=ignore;
}
}
int ans = 0;
for (int i = byebye.nextClearBit(0); i < N; i = byebye.nextClearBit(i+1)){
ans |= edges[i][2]; // whatever remains, OR that to answer
}
return ans;
}