The answer is $$$YES$$$ if and only if the number of red balls and the number of blue balls are both divisible by $$$2$$$.

The solution will not exist if $$$n < k$$$ because each letter must be used at least once. Further, if $$$k = 1$$$ and $$$n > 1$$$, the solution will not exist because each pair of adjacent characters must be different.

In all other cases, we can greedily construct the solution from left to right by maintaining number of characters not yet used, $$$r$$$; and the previous character, $$$prev$$$.To decide for the $$$i$$$-th position we do the following:

• If $$$r < n+1-i$$$, we can place the lexicographically smallest letter which is not equal to $$$prev$$$. (This will always be either "a" or "b".)
• Otherwise, we can place the smallest unused letter and decrease $$$r$$$ by $$$1$$$.

Time Complexity: $$$O(|A|*n)$$$ where $$$|A| = 26$$$ denotes the alphabet size.

It can also be done in $$$O(n)$$$ independent of $$$|A|$$$ but that is not required in this problem.

For any bit, how many numbers among the three can have it on?

Write N as sum of contributions of each bit.

For $$$a$$$ $$$XOR$$$ $$$b$$$ $$$XOR$$$ $$$c = 0$$$, it must be the case that each bit is either set in $$$0$$$ or $$$2$$$ among the three integers. Let us consider the set $$$S$$$ of the bit positions (starting with $$$0$$$ for least significant bit) which are set in exactly $$$2$$$ of these. We can now write: $$$N = 2*(\sum_{x \in S} 2^{x})$$$.

Clearly, if $$$N$$$ is odd no solution may exist. If $$$N$$$ is even, the above equation gives a representation of $$$\frac{N}{2}$$$ as a sum of distinct powers of $$$2$$$. This representation must be equivalent to the binary representation of $$$\frac{N}{2}$$$.

Therefore, we have uniquely recovered the set of bits which must be set in exactly two of the outputs. Now, we only need to distribute them among the three numbers. First of all, if $$$|S| = 1$$$, there can be no answer (all three outputs are required to be positive). Otherwise, let $$$i$$$ be the smallest member of $$$S$$$, then the following triple $$$(a, b, c) = (2^{i}, \frac{N}{2} - 2^{i}, \frac{N}{2})$$$ is the required answer. (This is obtained by greedily minimising $$$a$$$, followed by greedily minimising $$$b$$$.)

Time Complexity: $$$O(logN)$$$ per test case.

Can you solve for a fixed center vertex?

How many distinct center vertices are possible?

We can note the following:

• The center vertex must have degree $$$\geq K$$$.
• Two distinct $$$K$$$-stars can not share more than $$$1$$$ edge.

First of all, for simplicity, root the tree at $$$C$$$. Now, for every child $$$x$$$ of $$$C$$$, we can store an array $$$cnt_{x}$$$, where $$$cnt_{x}[d]$$$ will store the number of nodes in the subtree of $$$x$$$ at a depth $$$d$$$. After processing all children, we iterate over all possible depths $$$d$$$, and construct a temporary array $$$arr_{d}$$$ which contains the non-zero values of $$$cnt_{x}[d]$$$ over all $$$x$$$. The number of $$$K$$$-stars centred at $$$C$$$ with $$$dist(C, v_{corner}) = d$$$ is equal to the sum of products of all subsets of size $$$K$$$ of $$$arr_{d}$$$.

This can be easily computed using a dynamic programming with state:

$$$dp[i][j]$$$: the sum of products of all subsets of $$$j$$$ elements from the first $$$i$$$ elements

The dp takes $$$O(|arr_{d}|*K)$$$ time. Overall, $$$\sum_{d}|arr_{d}| \leq N$$$, therefore, the overall complexity is bounded by $$$O(NK)$$$. Combined with $$$O(\frac{N}{K})$$$ distinct possible centers, we get the final time complexity of $$$O(N^2)$$$ for each tree.