Mo's algorthm on tree 를 공부하고 있는데 왜 시간초과가 나는지 모르겠어서 질문합니다 ㅜㅜ

오일러 투어로 in, out을 구해놓은 뒤에

쿼리에 s, e가 주어지면 in[s] < in[e] 일때

i) lca(s, e) == s

오일러 투어의 in[s] ~ in[e] 구간을 찾도록 했고

ii) lca(s, e) != s

오일러 투어의 out[s] ~ in[e] 구간과 lca(s, e)만을 찾도록 했습니다

chk 배열은 19https://www.acmicpc.net/problem/13547 여기에 사용되는 것처럼 해당 숫자의 중복을 체크해주는 역할이고

cnt 배열은 구간에 포함된 id의 개수를 세주는 역할입니다. 포함될때, 제거할때 모두 1을 더해줌으로서 홀수일때는 a[id]를 포함시켜주고 짝수일때는 a[id]를 빼주는 방식으로 관리했습니다.

로직의 틀린점이나 시간초과가 나는 이유를 알수있을까요..