天天看點

Xor Path

先是看錯題目,以為是所有的路徑異或值的和,然後好像用了個假的print函數,一直wa,,,

既然是異或,那麼當一個點出現的次數是偶數次的時候它會被自己異或成零,也就是隊整體的答案沒有貢獻度,是以我們隻要統計有多少條路經過了這個點就行了。我們得到一個節點的每一個兒子的節點數量,然後再剩下不是目前節點中選擇一個節點,兩個建立一條邊,計算得到目前節點的兒子連兒子構成的最短路對這個點的貢獻度,然後再加上這個點與其兒子連結的貢獻度即可,如果是奇數則異或上我們的答案,否則這個點将會對答案沒有貢獻。