給定一顆無根樹 \(|T|\)。

求兩條點不相交的路徑，使得兩條路徑上邊權的異或和加起來最大。

這是一個經典 trick:

對于求兩條點不相交路徑，我們可以枚舉點 \(x\)，使得其中一條在 \(x\) 的子樹內，另外一條在 \(x\) 的子樹外。不難發現這樣覆蓋了所有的情況。

不妨以 \(1\) 為根。

那么對于這題，路徑上的異或和等于前綴和的異或，那么相當于子樹 內/外 選兩個點異或最大。

對于子樹內的情況，可以簡單 01trie 啟發式合并解決。復雜度 \(\mathcal O(n\log^2 n)\)。

對于子樹外的情況，我們先求出整個樹上異或和最大的路徑 \([x\rightarrow y]\)。

那么很明顯不在 \([1\rightarrow x]\cup[1\rightarrow y]\) 這個路徑上的點的答案就是這條路徑。

對于一個點，答案是整個樹扣掉 dfn 上他的區間。

那么對于一條路徑 \([1\rightarrow x]\) 上的每一個點，按深度從大往小考慮，他們的貢獻區間單調包含，那么可以直接維護，復雜度 \(\mathcal O(n\log n)\)。

總體復雜度 \(O(n\log^2 n)\)。

還有更好的辦法。

我們考慮假如子樹外的答案相同，那么我們只需要最大化子樹內的答案。

假如我們只考慮子樹內的答案，那么顯然一個點的祖先不會比他更劣。

假如我們把 \([1\rightarrow x]\cup[1\rightarrow y]\) 這條路徑扣掉，整棵樹會被分為若干個連通塊。

這樣，我們只需要考慮每個連通塊的根。這意味著每個點只會被插入到 01trie 一次。

時間復雜度 \(\mathcal O(n\log n)\)。