Maybe this problem 570D - Деревянные запросы have weak testcases!

Imagine this tree :

and these queries :

1 250001

2 250001

...

250000 250001

Now How 12519227 got ACCEPTED ! In function run , for(ans1..ans2) can be O(n). So this solution is O(n^2).

I checked it in polygon and it get TimeLimit even with 4 second.

I want to know, Is it OR I am wrong ??