題目的難度顏色使用 Luogu 上的分級，由簡單到困難分別為 🔴🟠🟡🟢🔵🟣⚫。

🔗 🔵 CF1709E. XOR Tree

Problem Statement

題目簡述

給定一棵含有 nn 個節點的樹，每個節點 ii 上寫有一個數值 aia_i。

如果樹中不存在任何一條簡單路徑，其路徑上所有節點的數值異或和為 00，則稱這棵樹是「好」的。

你可以執行以下操作任意次：選擇樹中的一個節點，將其數值替換為任意正整數。求使這棵樹變為「好」的所需的最少操作次數。

Constraints

約束條件

  • 1≤n≤2⋅1051 \le n \le 2 \cdot 10^5
  • 1≤ai<2301 \le a_i < 2^{30}
  • 保證給定的邊構成一棵樹。

思路：貪心 + 樹上啟發式合併

1. 如何計算簡單路徑的異或和？

首先，我們要如何快速計算樹上任意兩點 uu 和 vv 之間簡單路徑的點權異或和？

如果直接沿著樹爬行計算，每次查詢需要 O(n)\mathcal{O}(n) 的時間。為了優化，我們可以利用樹上異或前綴和的經典技巧：

  1. 任意指定一個節點（例如節點 11）作為根節點。
  2. 定義 dud_u 為從根節點到節點 uu 的簡單路徑上所有點權的異或和。

現在，如果我們直接將 dud_u 與 dvd_v 進行異或（即 du⊕dvd_u \oplus d_v），會發生什麼？

  • 從根節點到最近公共祖先 LCA(u,v)\text{LCA}(u,v) 的祖先路徑（不含 LCA\text{LCA} 本身）在 dud_u 和 dvd_v 中各被計算了一次。根據異或的自反性（x⊕x=0x \oplus x = 0），這部分路徑的異或和會被完全抵消。
  • LCA(u,v)\text{LCA}(u,v) 本身也在 dud_u 和 dvd_v 中各被計算了一次，同樣被抵消了。
  • 而 uu 到 LCA(u,v)\text{LCA}(u,v) 以及 vv 到 LCA(u,v)\text{LCA}(u,v) 的路徑（不含 LCA\text{LCA}）各被計算了一次，這正是我們需要的路徑部分。

因此，為了把被抵消的 LCA(u,v)\text{LCA}(u,v) 的點權 aLCA(u,v)a_{\text{LCA}(u,v)} 補回來， uu 到 vv 的簡單路徑異或和即為：

du⊕dv⊕aLCA(u,v)d_u \oplus d_v \oplus a_{\text{LCA}(u,v)}

題目要求任何簡單路徑的異或和都不能為 00，也就是說，對於任意兩點 uu 和 vv，必須滿足：

du⊕dv⊕aLCA(u,v)≠0  ⟺  du⊕dv≠aLCA(u,v)d_u \oplus d_v \oplus a_{\text{LCA}(u,v)} \neq 0 \iff d_u \oplus d_v \neq a_{\text{LCA}(u,v)}

這意味著，如果我們在樹中發現了某對節點 uu 和 vv，滿足 du⊕dv=aLCA(u,v)d_u \oplus d_v = a_{\text{LCA}(u,v)}，就說明它們之間的簡單路徑異或和為 00，這是不合法的，必須進行修改。

2. 考慮要如何修改？

如果我們發現某條路徑的異或和為 00，我們必須修改該路徑上的至少一個節點。為了讓修改的影響力最大（即一次修改能破壞儘可能多的不合法路徑），我們應該優先修改最近公共祖先（LCA）的數值。

為什麼修改 LCA 是最優的？

考慮自底向上的遍歷過程。如果我們在子樹內部發現了衝突，並在 LCA 處修改了節點值（例如修改為一個極大且獨一無二的數，如 230+node_id2^{30} + \text{node\_id}），這不僅能立即破壞當前子樹內所有經過該 LCA 且異或和為 00 的路徑，還能防止該子樹內部的節點與子樹外部的節點在更高層的祖先處再次形成異或和為 00 的路徑。

換句話說，修改 LCA 的值相當於將該子樹與外界完全「隔離」。因此，一旦我們修改了某個節點的值，我們就可以直接清空該節點對應的異或前綴和集合，因為它內部的節點再也無法與外界產生任何異或和為 00 的路徑。

3. 要如何檢查衝突？

既然要自底向上進行決策，我們可以使用後序遍歷（DFS）來維護每個節點對應子樹的異或前綴和集合。

對於當前節點 uu，我們需要將其所有子節點的集合進行合併。在合併的過程中，我們要如何檢查是否存在衝突？

假設我們當前已經累計了部分子樹的異或前綴和集合 SS，現在要併入另一個子節點的子樹集合 TT。

  • 對於 TT 中的任意一個異或前綴和 yy，如果它與 SS 中的某個值 xx 滿足 x⊕y=aux \oplus y = a_u，就說明存在一條經過 uu 且以 uu 為 LCA 的異或和為 00 的路徑。
  • 根據異或的性質，這個條件等價於：

    y⊕au=xy \oplus a_u = x

  • 因此，我們只需要遍歷集合 TT 中的每個元素 yy，檢查 y⊕auy \oplus a_u 是否存在於較大集合 SS 中即可。
  • 一旦發現存在，說明發生了衝突，我們必須修改 aua_u 的值。此時，我們直接將答案累加 11，並清空當前節點的集合（代表該子樹已被隔離），不再繼續與其他子節點合併。

4. 啟發式合併優化

如果我們在合併集合時，直接將子節點的集合併入父節點，最壞情況下（例如鏈狀樹）時間複雜度會退化至 O(n2)\mathcal{O}(n^2)。

樹上啟發式合併 (Heuristic Merge)

為了優化合併效率，我們採用啟發式合併：每次合併兩個集合時，總是將大小較小的集合併入較大的集合，並對較小的集合進行枚舉（即程式碼中的 if len(f) < len(nf): f, nf = nf, f）。

這樣做可以保證每個節點的異或前綴和最多被移動 O(log⁡n)\mathcal{O}(\log n) 次。在 Python 中，set 的查詢與插入平均時間複雜度為 O(1)\mathcal{O}(1)，因此整體的平均時間複雜度為 O(nlog⁡n)\mathcal{O}(n \log n)，可以輕鬆通過本題。

複雜度分析

  • 時間複雜度：O(nlog⁡n)\mathcal{O}(n \log n)。在樹上啟發式合併中，每個節點最多被合併 O(log⁡n)\mathcal{O}(\log n) 次。
  • 空間複雜度：O(n)\mathcal{O}(n)。在任意時刻，所有未被清空的集合中的元素總數不超過 nn，因此空間複雜度為 O(n)\mathcal{O}(n)。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
import sys

sys.setrecursionlimit(int(3e5))


def solve():
    n = int(input())
    A = list(map(int, input().split()))

    g = [[] for _ in range(n)]
    for _ in range(n - 1):
        u, v = map(lambda x: int(x) - 1, input().split())
        g[u].append(v)
        g[v].append(u)

    ans = 0

    def dfs(u: int, fa: int, val: int) -> set:
        val ^= A[u]
        f = {val}
        flag = False
        for v in g[u]:
            if v == fa:
                continue
            nf = dfs(v, u, val)

            if flag:
                continue

            if len(f) < len(nf):
                f, nf = nf, f
            for y in nf:
                if y ^ A[u] in f:
                    nonlocal ans
                    ans += 1
                    flag = True
                    f.clear()
                    break
            else:
                f.update(nf)
        return f

    dfs(0, -1, 0)
    print(ans)


if __name__ == "__main__":
    solve()