Editorial : Down the Pivot

The following matches the implementation in model_sol.cpp: global factorial inverses, Catalan numbers, per-query tail sums $P_x(A)=\sum_{j=0}^{A}\binom{x}{j}$, the convolution $\texttt{nless}(A)$, and answer $\texttt{nless}(K)-\texttt{nless}(K-2)$.

The program precomputes fact and ifact once, then Catalan numbers $\texttt{cat}[i]$ via $\binom{2i}{i}/(i+1)$ in the modular field.

For each test case it reads $n$ and $K$, sets $N=n-1$, and defines $\texttt{nless}(A)$: if $A < 0$ return $0$; otherwise build $\texttt{prec}[x]=P_x(A)=\sum_{j=0}^{A}\binom{x}{j}$ for $x=0,\ldots,N$ using $\texttt{prec}[0]=1$ and $\texttt{prec}[x]=2\,\texttt{prec}[x-1]-\binom{x-1}{A}$. It returns

The printed answer is $\texttt{nless}(K)-\texttt{nless}(K-2)$, which is the same weighted sum over splits $a$ as the closed form $\sum_{a}\texttt{Cat}(a)\texttt{Cat}(N-a)\big(P_a(K)P_{N-a}(K)-P_a(K-2)P_{N-a}(K-2)\big)$. Each query costs $O(n)$ after global preprocessing.

Let the root be $r$.

Each operation flips labels on a path that passes through $r$, so:

• root $r$ is flipped in every operation,
• on the left side we flip one path from left child down to some node (or nothing),
• on the right side similarly.

So left and right subtrees can be analyzed independently, then merged.

Take any rooted tree $T$ with root $s$ (this is one side of the original root).
Allowed side action: choose a node $v$ and flip path $s\to v$.

Define binary variables $x_u$ for nodes of $T$:

Then final label $y_u$ is:

This linear transform is invertible:

(missing child contributes $0$).

Hence for a side with $m$ nodes:

• each labeling corresponds to exactly one $x$-vector,
• required number of side endpoints is exactly $s=\sum x_u$,
• number of side labelings with endpoint-count $s$ equals $\binom{m}{s}$.

So this count depends only on $m$, not on shape.

For whole tree with left size $a$ and right size $b$ ($a+b=n-1$):

• left needs $s_L$ endpoints,
• right needs $s_R$ endpoints.

One global operation can carry at most one left endpoint and one right endpoint, so minimal operation count before root parity is:

Root label $r$ must satisfy:

Therefore for fixed $(s_L,s_R)$:

• one choice of root bit gives cost $m_0$,
• the other gives cost $m_0+1$.

This is useful intuition before counting all trees.

Suppose one concrete binary tree shape is fixed, and one concrete label assignment is fixed.
How do we compute the minimum number of operations $k$ for this specific instance?

Ignore left/right split for a moment. Consider just one rooted binary tree:

• each node has bit $y_u$,
• one operation chooses a node $v$ and flips all bits on path $\text{root} \to v$,
• target is all zeros.

Define $x_u$ as parity of how many times $u$ is chosen as an endpoint:

A node $u$ is flipped by exactly those endpoints inside $\text{subtree}(u)$, so:

This can be inverted locally:

where missing child contributes $0$.

Why this formula is true:

Write subtree equations for $u$ and its children:

Now XOR these three equations:

Every $x_t$ inside left subtree appears twice (in $y_u$ and $y_{lc(u)}$), so it cancels.
Every $x_t$ inside right subtree also appears twice (in $y_u$ and $y_{rc(u)}$), so it cancels.
Only $x_u$ appears exactly once (only in $y_u$), therefore:

This is exactly the same as “parent subtree XOR minus children subtree XORs” in XOR arithmetic.

So we can compute all $x_u$ in $O(n)$, and the minimum operation count is simply:

because each $x_u=1$ endpoint must be used odd times (at least once), and using exactly once is enough.

This is the exact core that we apply separately to left and right sides in the original problem.

Your intuition is correct for the mini-problem above:

• if one operation is only root -> endpoint,
• then minimum operations equals number of ones in transformed vector ($\sum x_u$).

But for original problem G, one operation is a whole path through root, so it can serve both sides at once. That means we do not pay $\sum x_u$ globally. Instead:

• left side contributes $s_L=\sum x^L_u$,
• right side contributes $s_R=\sum x^R_u$,
• one operation can satisfy one left demand and one right demand simultaneously.

So base cost is:

not $s_L+s_R$.

Then root parity decides whether final cost is $m_0$ or $m_0+1$.

So the counting target is not “binary trees with exactly $k$ ones in transformed tree”. The correct counting target is:

• count assignments where $\max(s_L,s_R)$ and root parity combine to exactly $k$.

1. Compute endpoint-parity vectors on both sides via the inverse transform: $$ x_u = y_u \oplus y_{lc(u)} \oplus y_{rc(u)}. $$
2. Let: $$ s_L=\sum x^L_u,\qquad s_R=\sum x^R_u. $$
3. Base operation count needed to realize side endpoints: $$ m_0=\max(s_L,s_R). $$ (Lower bound because one operation contributes at most one endpoint per side; achievable by pairing side demands greedily.)
4. Enforce root parity ($r$ is the root label): $$ k= \begin{cases} m_0, & m_0 \equiv r \pmod 2,\\ m_0+1, & \text{otherwise}. \end{cases} $$

So for a fixed tree and fixed labels, $k$ is obtained in linear time.

In problem D (array), we used a boundary-difference transform:

• original bits $b$ on positions,
• boundary bits $c$ on cuts,
• flipping interval $[l,r]$ changes only two boundaries: $c_{l-1}$ and $c_r$.

So a long-range operation in original space becomes a very sparse update in transformed space.

The same philosophy works on trees.

For a rooted binary tree, define:

This is the tree version of “difference on boundaries” (a local discrete derivative / divergence).

Then:

which is the tree analogue of “prefix/suffix reconstruction from diff”.

First, simpler operation: flip path $\text{root}\to v$.

• For every internal node on that path (except $v$), both $y_u$ and exactly one child term in $x_u$ are toggled, so $x_u$ does not change.
• At endpoint $v$, $y_v$ toggles but no child-on-path term toggles, so $x_v$ flips.

So root-to-node flip changes exactly one transformed value: $x_v$.

This is even cleaner than array interval flip (2 boundaries): on a rooted tree, this operation is 1-point toggle in $x$-space.

Now original operation in problem G is a path through root (left endpoint and right endpoint). You can view it as:

• one root-to-left-endpoint flip,
• one root-to-right-endpoint flip,
• and a root-only parity correction.

Hence in transformed variables it corresponds to toggling endpoint-parity coordinates on left/right, while root parity is handled separately (the $m_0$ vs $m_0+1$ step).

That is exactly why the optimization becomes:

• count needed endpoint parities on each side,
• combine by $\max(s_L,s_R)$,
• then fix root parity.

Think of one root-to-node flip as:

• choose one endpoint node $v$,
• send one toggle “wave” from $v$ upward to the root.

Now imagine doing many operations.
For any node $u$, only one thing matters: how many endpoint choices were made inside $\text{subtree}(u)$, modulo $2$.

So instead of tracking labels directly, track endpoint parities (“tokens”) at nodes:

• operation = place one token at one endpoint,
• effect on labels = each node reads parity of tokens in its subtree.

This is why the transformed representation is sparse for this operation type:
each operation changes exactly one endpoint-parity coordinate.

Contrast with subtree flips:

• subtree flip has a single boundary edge, so edge-diff (node xor parent) is sparse;
• root-path flip has a single endpoint choice, so endpoint-parity transform is sparse.

Always pick a transform whose coordinates match the primitive choice of one operation.

Define:

with $P_m(k)=0$ for $k<0$.

For fixed $(a,b)$:

• pairs with $\max(s_L,s_R)\le k$ are $P_a(k)P_b(k)$,
• so pairs with exact max $k$ are $$ D_k=P_a(k)P_b(k)-P_a(k-1)P_b(k-1). $$

Cost $k$ receives:

• max $k$ with one root parity,
• max $k-1$ with the opposite parity.

Thus:

Now multiply by number of ordered binary-tree shapes on each side:

Final formula:

Precompute up to $\max n$:

• factorial / inverse factorial for combinations,
• Catalan numbers.

For each query $(n,k)$:

1. Build arrays for $a=0..n-1$: $$ P_a(k),\quad P_a(k-2). $$ Use recurrence: $$ P_{a+1}(k)=2P_a(k)-\binom{a}{k}, $$ so each array is $O(n)$.
2. Evaluate the summation over $a$ in $O(n)$.

Given $\sum n\le 10^6$, this is fast enough.