Fenwick tree is much faster than a regural segment tree, and segment tree without lazy propagation can me much faster than the one with lazy propagation. Also the up-to-bottom implementation of segment tree can be substantially slower than the bottom-to-top one.

Also note that in your implementation of Euler tour each vertex is put twice in the array. This is not needed, however: one time (either at the beginning or at the end of the dfs procedure) is enough.

So I definitely feel for you, but I have to admit there is enough room for optimization in your solution. My approach gets OK in 295 ms: 230557194. If I were a problemsetter, I would try to loosen TL as much as possible, and your solution would probably get OK as well.

P.S. The editorial proposes the same approach I used.