\(X_i,Y_i\) を増やす操作をそれぞれ偶数移動,奇数移動と呼ぶことにします．

まず目標が可能かどうか判定します．

各奇数移動について，その直前に偶数移動 があるはずです． よって，奇数移動と偶数移動をマッチングさせ，奇数移動が余る場合，目標は達成不可能です．

そうでないときはマッチングを長さ \(2\) のウォークとして使うことで目標を達成することはできます．

\(X_i=Y_i=0\) となる辺で木を分割し，連結成分ごとに別々に解くことにします． 各頂点 \(v\) に対し，\(f_v=\) 隣接辺の \(X_i-Y_i\) の総和 と定義します．

連結成分内に \(f_v \neq 0\) となる頂点が存在しない場合，すべての辺で \(X_i=Y_i\) が成立しており，この連結成分は \(1\) つのウォークで全部達成できます（連結成分が \(1\) 頂点からなる場合は \(0\)）．

そうでないとき，この連結成分では，少なくとも \(W=(\sum_{v} |f_v|)/2\) 個のウォークが必要です． そしてこの下界 \(W\) は実際に達成可能です．

これは次のように示せます． まず最初のマッチングをもとに適当な解を作成します． ある頂点を見たときに，そこを端点とし奇数移動で接続しているウォークと，偶数移動で接続しているウォークが両方あったとします． するとこの \(2\) つのウォークは連結することができます． この操作を繰り返すと，\(W\) 個の閉じないウォーク \(+\) \(0\) 個以上の閉じたウォークが得られます． ここで，閉じたウォークを別のウォークの中に挿入することができます．これは共通して通る頂点があれば可能です． 連結成分の作り方から，すべての閉じたウォークを閉じないウォークに収納することができることがわかります． これで示せました．

以上を実装すれば，\(O(N)\) 時間の解法になります．

回答例(C++)