[test case] more tall trees for jump on tree

[lrvideckis]

https://github.com/yosupo06/library-checker-problems/blob/master/tree/jump_on_tree/gen/max_random.cpp#L208

doing this results in trees with logn expected height, correct? so the only tests are either line/linked list, and trees with logn height

What if we added a test case which isn't line but has linear height? I̶ d̶o̶n̶'t̶ h̶a̶v̶e̶ a̶ s̶p̶e̶c̶i̶f̶i̶c̶ b̶u̶g̶ i̶n̶ m̶i̶n̶d̶

idea 1: for(int i=1;i<n;i++) par[i] = gen.uniform(max(0,i-k), i - 1); where k is in [1,10] maybe (k=1 gives linked list, and the lower the k-value, the higher the expected tree height)

idea 2: generate line of size n/2, then add n/2-1 more random edges

[lrvideckis]

well actually here's potentially a bug: if you do a vertical path decomposition by deepest leaf, then as you walk up the paths, there will be O(sqrt(n)) of them. but not if the tree has logn height. (and line case, there is a single vertical path)

[lrvideckis]

here's a O(nq) solution which AC's but shouldn't

https://judge.yosupo.jp/submission/243149

basically it's HLD, but you choose an arbitrary child instead of child-with-largest-subtree to extend each vertical path. So there are O(n) vertical paths as you walk up towards the root.

but tests have logn expected height, so it passes in this case. And it passes line case because it's a single vertical path

[lrvideckis]

you should add this test to LCA as well

https://judge.yosupo.jp/submission/243154

[lrvideckis]

the case that results in O(n) vertical paths when traversing upwards looks like:

[maspypy]

Thank you.
I have added test cases for the LCA, and I was able to confirm that your submission results in TLE.

#1257
https://judge.yosupo.jp/submission/243154

I will now make similar additions for jump on tree.