グラフが連結であるという条件から、頂点 \(1\) に書き込む数を決めると、全ての頂点について書き込む数が(存在するなら)一意に決まります。

また、頂点 \(1\) に書き込む数を \(x\) としたとき、頂点 \(i\) に書き込む数は \(p_i+x\) または \(q_i-x\) の形で表されます。したがって、各頂点についてこれらの表現を求め、その全ての値が \(0\) 以上になる \(x\) が存在するか判定すれば良いです。前者の表現は \(x\geq -p_i\)、後者は \(x\leq q_i\) を導くので、条件を満たすような \(x\) は区間として表すことができ、存在判定は高速に行えます。

なお、\(1\) つの頂点に \(p_i+x\) 型と \(q_i-x\) 型の両方の表現がある場合には、\(\displaystyle x=\frac{q_i-p_i}{2}\) と一意に定まることに注意してください。