{"trustable":true,"sections":[{"title":"","value":{"format":"HTML","content":"\u003cdiv\u003e\u003cp\u003eIn an edge-weighted tree, the xor-length of a path \u003ci\u003ep\u003c/i\u003e is defined as the xor sum of the weights of edges on \u003ci\u003ep\u003c/i\u003e:\u003c/p\u003e\u003ccenter\u003e\u003cimg src\u003d\"CDN_BASE_URL/8309a6bdc627b88cd7c9ccccb5d76e8c?v\u003d1715674334\" alt\u003d\"_{xor}length(p)\u003d\\oplus_{e \\in p}w(e)\" align\u003d\"absmiddle\"\u003e\u003c/center\u003e\u003cp\u003eā is the xor operator.\u003c/p\u003e\u003cp\u003eWe say a path the xor-longest path if it has the largest xor-length. Given an edge-weighted tree with n nodes, can you find the xor-longest path? ć\u003c/p\u003e\u003c/div\u003e"}},{"title":"Input","value":{"format":"HTML","content":"\u003cdiv\u003e\u003cp\u003eThe input contains several test cases. The first line of each test case contains an integer \u003ci\u003en\u003c/i\u003e(1\u0026lt;\u003d\u003ci\u003en\u003c/i\u003e\u0026lt;\u003d100000), The following \u003ci\u003en\u003c/i\u003e-1 lines each contains three integers \u003ci\u003eu\u003c/i\u003e(0 \u0026lt;\u003d \u003ci\u003eu\u003c/i\u003e \u0026lt; \u003ci\u003en\u003c/i\u003e),\u003ci\u003ev\u003c/i\u003e(0 \u0026lt;\u003d \u003ci\u003ev\u003c/i\u003e \u0026lt; \u003ci\u003en\u003c/i\u003e),\u003ci\u003ew\u003c/i\u003e(0 \u0026lt;\u003d \u003ci\u003ew\u003c/i\u003e \u0026lt; 2^31), which means there is an edge between node \u003ci\u003eu\u003c/i\u003e and \u003ci\u003ev\u003c/i\u003e of length \u003ci\u003ew\u003c/i\u003e. \u003c/p\u003e\u003c/div\u003e"}},{"title":"Output","value":{"format":"HTML","content":"For each test case output the xor-length of the xor-longest path."}},{"title":"Sample","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e4\r\n0 1 3\r\n1 2 4\r\n1 3 6\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e7\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}},{"title":"Hint","value":{"format":"HTML","content":"\u003cdiv\u003e\u003cp\u003eThe xor-longest path is 0-\u0026gt;1-\u0026gt;2, which has length 7 (\u003d3 ā 4) \u003c/p\u003e\u003c/div\u003e"}}]}