HDU 5274 Dylans loves tree：LCA + 線段樹維護路徑異或值

問題建模

給定一棵樹，每個節點有值 A[i]。支持兩種操作：
1. 0 x y：將節點 x 的值改為 y。
2. 1 x y：查詢路徑 x→y 上所有值的出現次數奇偶性，保證最多一個值出現奇數次，輸出該值或 -1。

核心觀察：路徑異或性質

定義 Xor[u] 為根到 u 路徑上所有值的異或和。則路徑 u→v 的異或和為：
Xor[u] ^ Xor[v] ^ A[LCA(u,v)]
若所有值出現偶數次，異或和為 0；否則異或結果即為唯一出現奇數次的值。

動態修改處理：子樹區間異或更新

修改節點 u 的值從 old 變為 nw，影響以 u 為根的子樹內所有節點的 Xor 值。利用 DFS 序將子樹映射為連續區間 [dfn[u], dfn[u]+sz[u]-1]，線段樹支持區間異或更新、單點查詢。

線段樹懶標記設計

• 每個節點存儲該區間的異或懶標記 tag。
• 下推時：tag[ls] ^= tag[o]; tag[rs] ^= tag[o];
• 單點查詢：從根遞歸下推至葉子，累積 tag 異或到初始 Xor。

LCA 預處理：RMQ (ST 表)

DFS 記錄歐拉序 euler[] 與深度 dep[]，first[u] 為 u 首次出現位置。LCA(u,v) = euler[RMQ(first[u], first[v])]。

完整流程

1. 讀入樹，DFS 計算 dfn、sz、Xor、歐拉序。
2. 構建 ST 表支持 O(1) LCA。
3. 線段樹初始化（全 0 懶標記）。
4. 處理查詢：
   　修改：區間異或 old ^ nw。
   　查詢：取兩端點 Xor 異或再異或 A[LCA]，結果為 0 輸出 -1，否則輸出值。
   

複雜度

預處理 O(N log N)，單次操作 O(log N)，總 O((N+Q) log N)，滿足 N,Q ≤ 1e5。