꽃 배달

Root the tree at vertex $1$ and index the flower shops from $0$ to $K-1$. Let $m_v$ be the bitmask of shops in the subtree of $v$. Obtain every mask in $O(N)$ time by OR-ing child masks into parent masks.

After visiting a set $S$ of shops, the traversed vertices are precisely the union of the root-to-shop paths for shops in $S$. Hence the number of flowers picked is $F(S)=\sum_{v:(m_v\mathbin{\&}S)\ne0}a_v$. Exactly flowers have been sold, so the prefix set is feasible if and only if .

Define $b[T]=\sum_{v:m_v=T}a_v$ and . Using SOS DP, compute . Then , where XOR takes the complement of within the bits.

Let $dp[S]$ be the number of successful orders that visit precisely the shops of $S$. Set $dp[0]=1$. For nonempty $S$:

$$dp[S]=\begin{cases}0,&F(S)<|S|,\\\sum_{i\in S}dp[S\setminus\{i\}],&F(S)\ge |S|.\end{cases}$$

The summands partition orders by the last shop $i$. Take every sum modulo $998\,244\,353$. The answer is $dp[(1\ll K)-1]$.

Time complexity is $O(N+K2^K)$, space complexity is $O(N+2^K)$, and the total flower count is at most , which fits in signed 64-bit arithmetic.

Solution written by GPT6