Hints: Down the Pivot

Read $n$ and $K$. Set $N=n-1$ (nodes strictly below the root in the pivot tree) and precompute Catalan numbers $\texttt{cat}[i]=\frac{1}{i+1}\binom{2i}{i}$ for $i=0,\ldots,N$ modulo $10^9+7$.

For nonnegative $A$, define tail sums $P_m(A)=\sum_{j=0}^{A}\binom{m}{j}$. Build $\texttt{prec}[x]=P_x(A)$ for $x=0,\ldots,N$ with $\texttt{prec}[0]=1$ and, for $x \ge 1$,

$$ \texttt{prec}[x]=2\,\texttt{prec}[x-1]-\binom{x-1}{A}. $$

If $A < 0$, treat $\texttt{nless}(A)$ as $0$ without building $\texttt{prec}$.

Define

$$ \texttt{nless}(A)=\sum_{x=0}^{N}\texttt{cat}[x]\,\texttt{cat}[N-x]\,\texttt{prec}[x]\,\texttt{prec}[N-x], $$

using the $\texttt{prec}$ array built for that fixed $A$.

The final answer is $\texttt{nless}(K)-\texttt{nless}(K-2)$. Expanding both sums yields $\sum_{a=0}^{N}\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)$.

Precompute factorials and inverse factorials once up to about $2.1\cdot 10^6$; $\texttt{ncr}(n,k)$ returns $0$ if $k < 0$ or $k > n$, and feeds every Catalan and binomial in $\texttt{nless}$.

Root is special: every allowed path always passes through the root, so each operation always toggles the root bit.

Try to understand what happens independently inside the left and right subtrees.

Fix one side (say a rooted subtree with top node $s$).
If an operation chooses endpoint $v$ on this side, it toggles exactly nodes on path $s \to v$.

So side operations are “toggle root-to-node paths” in that subtree.

For that side, define binary variables $x_u$:

• $x_u=1$ means we use endpoint $u$ odd number of times.

Then resulting label $y_u$ on node $u$ is:

$$ y_u = \bigoplus_{v \in \text{subtree}(u)} x_v. $$

This transform is invertible.

Answer to Hint 3:
Because the transform is bijective over $\mathbb{F}_2$, for a fixed side of size $m$:

• every labeling corresponds to exactly one $x$-vector,
• and required number of side-endpoints is exactly $s=\sum x_u$.

So count of side labelings with endpoint-count $s$ is simply:

$$ \binom{m}{s}. $$

Now combine two sides.

Let:

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

One global operation can carry at most one left endpoint and at most one right endpoint, so minimum operations before root-parity constraint is:

$$ m_0 = \max(s_L, s_R). $$

Root label $r$ must match operation parity:

$$ r \equiv \#\text{operations} \pmod 2. $$

So with fixed $(s_L,s_R)$:

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

Fixed-tree viewpoint: suppose the tree shape is fixed and labels are fixed.
How do we compute the minimum operation count $k$ for this one tree?

Recover endpoint parities on each side from labels using:

$$ x_u = y_u \oplus y_{lc(u)} \oplus y_{rc(u)}. $$

Then:

$$ s_L=\sum x^L_u,\qquad s_R=\sum x^R_u,\qquad m_0=\max(s_L,s_R). $$

Finally enforce root parity:

$$ k= \begin{cases} m_0, & m_0 \equiv r \pmod 2,\\ m_0+1, & \text{otherwise}. \end{cases} $$

Why this fixed-tree formula is correct:

• each operation can contribute at most one chosen endpoint per side, so at least $\max(s_L,s_R)$ operations are needed;
• this bound is achievable by pairing left and right endpoint-needs greedily (and using “empty” on one side for leftovers);
• root flips every operation, so operation count parity must equal root bit.

So for a fixed tree, $k$ is computable in linear time once $x$ is known.

Fix subtree sizes $a$ and $b$ ($a+b=n-1$).
Let:

$$ P_m(k)=\sum_{i=0}^{k}\binom{m}{i}. $$

For this split, number of side assignments with $\max(s_L,s_R)\le k$ is:

$$ P_a(k)\,P_b(k). $$

So exact max equal to $k$ is:

$$ D_k=P_a(k)P_b(k)-P_a(k-1)P_b(k-1). $$

Cost $k$ comes from:

• max $=k$ with matching root parity, or
• max $=k-1$ with opposite root parity.

So for fixed $(a,b)$:

$$ A_k = D_k + D_{k-1} = P_a(k)P_b(k)-P_a(k-2)P_b(k-2). $$

Multiply by number of ordered tree shapes on each side:

$$ \text{Cat}(a)\cdot\text{Cat}(b), $$

where

$$ \text{Cat}(m)=\frac{1}{m+1}\binom{2m}{m}. $$

Final formula:

$$ \text{ans}(n,k)= \sum_{a=0}^{n-1} \text{Cat}(a)\text{Cat}(n-1-a) \Big(P_a(k)P_{n-1-a}(k)-P_a(k-2)P_{n-1-a}(k-2)\Big). $$

Implementation details:

1. Precompute factorials/inverse factorials up to $2\max n$.
2. Precompute Catalan numbers up to $\max n$.
3. For each query, build arrays $P_a(k)$ and $P_a(k-2)$ for $a=0..n-1$ in $O(n)$ using: $$ P_{a+1}(k)=2P_a(k)-\binom{a}{k}. $$
4. Evaluate the sum over $a$ in $O(n)$.

Total complexity over all tests: $O\!\left(\sum n\right)$ after precomputation.