I’m attempting this problem, and my code is here.
While it succeeds on the sample test case, it fails on all the rest of the test cases (wrong answer). It uses an iterative Euler tour and calculates the XOR of the path to each of the nodes along with the LCA for the answer with a segment tree.
I can’t seem to find what I did wrong. Any help?
Did you try finding a small counter-test?
Yeah… turns out (after copy pasting some other USACO sample trees) that the problem lied in generating the Euler tour. I wasn’t adding the leaf nodes twice, and doing that made it pass just barely under the time limit, like 3988 ms.
Thanks so much!
But I have a nagging feeling that this could be made much faster… any suggestions? (Fixed code is here)