公式解説 と異なり、重み付きUnionFindを使わない解法です。

3 つ組 (\(a_i\)​,\(b_i\)​,\(d_i\)​) を \( i=1,2,\dots,Q\) の順に見て、 \(a_i\) と \(b_i\) が非連結だった場合に \(a_i\) と \(b_i\) を辺で結ぶことにします。すると、この操作を行った \(i\) は出力すべき答えに含まれます。

そのような \(i\) だけを用いて構築したグラフの各連結成分に対し、ひとつの頂点からBFSなどをして各頂点に対する \(X\) の値のうちvalidなものを一つ定めることができます。

最後にもう一度クエリを見て、\( i=1,2,\dots,Q\) のうち \(X\) の値のつじつまが合っているものを出力すれば良いです。

実装例