\(T_i=0\) のとき， \(X_i+1=Y_i\) という制約がなくても解ける方法です．

これには weighted union find を加工したものを用います．通常の weighted union find は以下のようなデータ構造です．

配列 \((A_1,A_2,\dots,A_N)\) について，以下のクエリを処理せよ．

• \(i,j,d\) が与えられる． \(A_i-A_j=d\) という条件が付与される．
• \(i,j\) が与える．\(A_i-A_j\) の値が定まるか，さらに定まるならその値を求めよ．

これの実現方法を考えます．

まず， \(N\) 頂点のグラフ \(G\) を考えます． \(1\) 番目のクエリについて， \(G\) の頂点 \(i,j\) に辺を張ることを考えます．このとき，各辺 \((u,v)\) は \(A_u,A_v\) のうち一方が定まればもう一方も定まることを表します．よって， \(2\) 番目のクエリについて， \(G\) の頂点 \(i,j\) が連結であることと， \(A_i-A_j\) が定まることは同値です．これは union find そのものです．

また，具体値も求める必要があります．これは， union find の各辺 \((x,y)\) について \(x-y\) の値を持つことで，その和として求められます．

これを，情報の持ち方を拡張し， \(x+cy=d(c\in\{-1,1\})\) という情報を持つことにすると，本問題を解くことができます．

計算量は， union find の償却計算量を \(\text{uf}(n)\) として \(O(N\text{uf}(N))\) です．工夫すると \(\text{uf}(n)=\alpha(N)\) とできますが \(\log(N)\) でも十分高速です．