I think it's just some complicated combinatorics.

I submitted using atcoder::convolution and it got WA on 3 tests (AC on the rest). Seems weird.

Same question here. AC 57 tests and failed 3 tests. While NTT on half of the polynomial got AC.

I think NTT doesn't work for really big cases because the largest $$$2^n$$$th root of unity you can make in the finite field of order $$$998244353$$$ is $$$2^{23} \lt 10^7$$$. So then the NTT just calculates nonsense.

Here's the link to editorial (Japanese). I guess you can just read the math formulas. Link

We want the value of leaf of a subtree be consecutive.

    1
   / \
  2   3
 / \ 
4   5

We want vertex 4 and 5 {(1, 1) and (2, 2)} or {(2, 2) and (3, 3)} but not {(1, 1) and (3, 3)}.

tho i may be wrong i think what happens is that when u mark all leaves with num, num, you end up with the parent having a range larger than it should be. for example, because you dont mark leaves in dfs order, if a parent has children 2, 3, 5 that are all leaves, it may mark 2 as (1,1), 2 as (2,2), and 5 as (4,4), thus including leaf node marked (3,3) in the process.

EDIT: oops someone beat me to it lol

Let dp[i] be the set of position that we can reach when moving i steps. Initially, dp[0] = {0}. for i != 0, we iterate over dp[i-1]. Let P be some value in dp[i-1], we add P + a[i] and P + b[i] to set dp[i]. The answer is to find if X is in dp[n]. Submission

Oh, I think I made this assumption too, but my solution got AC.

I think it is part of that problem to translate the formulars into some meaningful.

From my point of view we can output all segements as l[i]=r[i]=1, that would satisfiy all conditions and would obviously minimize the max used value.

Unfortunatly the editorial does not cover that part.

Can somebody explain?

the first condition is really just saying for two nodes i and j, Li,Ri must be completely inside or intersect with Lj,Rj if j is an ancestor of i

the second one says their L and R values must not intersect if i and j are in different subtrees

Both are the coeff of x^b in (1+x)^(a+c)

You can think of the left term as a two-step process in which, you want to select $$$b$$$ elements from two sets. First, you choose $$$i$$$ element from $$$c$$$ then you choosing $$$b-i$$$ from $$$a$$$. This is equivalent to choosing $$$b$$$ directly from $$$a+c$$$ (it has a one-to-one mapping to the above two-step process)