CF1586 E. Moment of Bloom

題目描述

n點m邊的無向連通圖，q次詢問，每次給定u,v，你可以對u到v的一個簡單路徑的所有邊進行+1操作。你需要判斷能否使得所有邊權都為偶數，如果可以，請輸出所有操作的路徑上的點。如果不行，輸出至少還需要多少操作才能使得上述結果。

資料範圍

$n \times q,m \le 3 \times 10^5$

題解

是我永遠不會的構造題。

考慮到如果一個點在詢問中出現奇數次，那肯定是不可以的。

是以考慮到所有點在詢問中出現偶數次，那就可以考慮生成樹，然後每個詢問直接走樹邊即可。因為如果一條邊是奇數次的話，那肯定某個點在詢問中出現奇數次，沖突。

效率： $O(nq+m)$ 。