P6072 "MdOI R1" Path

You are given an undirected tree with $n$ nodes, and each edge has a weight. Let $V(x,y)$ and $E(x,y)$ denote the set of all nodes and the set of all edges on the simple path between $x$ and $y$ in the tree. In particular, when $x=y$, $V(x,y)=\{x\}$ and $E(x,y)=\varnothing$. Define the weight $f(E)$ of an edge set $E$ as the **bitwise XOR sum** of the weights of all edges in $E$. When $E=\varnothing$, $f(E)=0$. Now, you need to compute $$ \max_{1\le x,y,u,v \le n,V(x,y)\cap V(u,v) = \varnothing}(f(E(x,y)) + f(E(u,v))) $$ In plain words, you need to choose two simple paths such that they do not share any common nodes, and the sum of their edge-weight XOR values is as large as possible.

The first line contains an integer $n$, the number of nodes in the tree. The next $n-1$ lines each contain three integers $x,y,w$, indicating that there is an edge of weight $w$ between nodes $x$ and $y$.

Output one integer on a single line, the answer.

[Sample 1 Explanation] The tree in the sample is shown in the figure. Choose the two paths marked in red and blue. They have no common nodes, and the sum of XOR values is maximized, which is $(7\oplus 1\oplus 8)+(5\oplus 2)=21$ (where $\oplus$ denotes the XOR operation).  [Sample 2 Explanation] The tree in the sample is shown in the figure. It is a chain. Choose the red and blue paths; the blue path degenerates into a single node, making the maximum sum of XOR values $2+0=2$. Note that the red path cannot be extended to $3$, otherwise the blue path would not be possible.  --- [Constraints] **This problem uses bundled testdata.** | Subtask ID | $n\leq$ | Special Property | Score | Time Limit | | :--------: | :------------: | :--------------: | :---: | :--------: | | 1 | $50$ | None | 12 | 1s | | 2 | $2\times 10^3$ | None | 28 | 2s | | 3 | $2\times 10^4$ | $y = x + 1$ | 20 | 3s | | 4 | $3\times 10^4$ | None | 40 | 3.5s | For $100\%$ of the testdata, $2\leq n\leq 3\times 10^4$, $1\leq x,y\leq n$, $0\leq w\leq 10^9$. # Input Format The first line contains an integer $n$, the number of nodes in the tree. The next $n-1$ lines each contain three integers $x,y,w$, indicating that there is an edge of weight $w$ between nodes $x$ and $y$. # Output Format Output one integer on a single line, the answer. # Hint [Sample 1 Explanation] The tree in the sample is shown in the figure. Choose the two paths marked in red and blue. They have no common nodes, and the sum of XOR values is maximized, which is $(7\oplus 1\oplus 8)+(5\oplus 2)=21$ (where $\oplus$ denotes the XOR operation).  [Sample 2 Explanation] The tree in the sample is shown in the figure. It is a chain. Choose the red and blue paths; the blue path degenerates into a single node, making the maximum sum of XOR values $2+0=2$. Note that the red path cannot be extended to $3$, otherwise the blue path would not be possible.  --- [Constraints] **This problem uses bundled testdata.** | Subtask ID | $n\leq$ | Special Property | Score | Time Limit | | :--------: | :------------: | :--------------: | :---: | :--------: | | 1 | $50$ | None | 12 | 1s | | 2 | $2\times 10^3$ | None | 28 | 2s | | 3 | $2\times 10^4$ | $y = x + 1$ | 20 | 3s | | 4 | $3\times 10^4$ | None | 40 | 3.5s | For $100\%$ of the testdata, $2\leq n\leq 3\times 10^4$, $1\leq x,y\leq n$, $0\leq w\leq 10^9$。 Translated by ChatGPT 5