Maximum XOR Sum of Two Disjoint Paths

You are given an unrooted tree with n nodes. Each edge in the tree has an associated weight. For any two nodes x and y, let \(V(x,y)\) denote the set of all nodes on the unique simple path between x and y (with the convention that when x=y, \(V(x,y)=\{x\}\)), and let \(E(x,y)\) denote the set of edges on that simple path (with \(E(x,x)=\varnothing\)).

Define a function on any set of edges \(E\) as:

[ f(E)=\bigoplus_{e\in E}w(e), \quad \text{with } f(\varnothing)=0, ]

where \(\oplus\) denotes the bitwise XOR operation.

The goal is to choose two simple paths (which may be trivial paths containing a single node) such that they do not share any common nodes, i.e., \[ V(x,y)\cap V(u,v)=\varnothing, \] and maximize the quantity:

[ \max_{1\le x,y,u,v\le n,,V(x,y)\cap V(u,v)=\varnothing}\Bigl(f(E(x,y))+f(E(u,v))\Bigr). ]

In other words, find two disjoint paths in the tree (they may be degenerate paths of length 0) so that the sum of the XOR sums of their edge weights is maximized.

inputFormat

The first line contains a single integer n, the number of nodes in the tree.

Each of the following n-1 lines contains three space‐separated integers u, v, and w representing an edge between nodes u and v with weight w. It is guaranteed that the graph forms a tree. The nodes are numbered from 1 to n.

outputFormat

Output a single integer, the maximum possible sum \(f(E(x,y))+f(E(u,v))\) for two disjoint simple paths in the tree.

sample

3
1 2 1
2 3 2

2