Do we need to return to the root after visiting $$$k$$$ restaurants?

الراجل ده بيتكلم صح

Probably unsolvable, but for starters, you can solve for small $$$k$$$ using bitmask dp.

So we have a tree with $$$m$$$ black nodes are your goal is to go through $$$k$$$ black nodes.

Consider two kinds of strategies:

1. Go to a black vertex and start moving to an adjacent non-black node back and forth until you arrive at $$$k$$$ black nodes visited.
2. Go to a black vertex and start moving to an adjacent black node back and forth until you arrive at $$$k$$$ black nodes visited.

The path follows one of these strategies, I leave the proof to the reader but it's a simple contradiction.

For each node precompute its distance to the root and the number of black nodes in this path with a simple DP. Now, for each black node try strategy 1 with its lower-weighted adjacent non-black node and strategy 2 with its lower-weighted adjacent black node.

I guess that you meant that the rooted-tree is weighted-edge, i.e. each edge has a weight associated with walking through it one time. Is that right?

I was thinking $$$dp[v][k][f] =$$$ min cost if you have to pick $$$k$$$ vertices from the subtree of $$$v$$$, and $$$f$$$ is 1 if you have to go all the way back to the root $$$v$$$ after getting the $$$k$$$ specials and $$$0$$$ if not.

Then we could solve this with a convolution on tree (similar to this problem): $$$dp[v][a + b][0] = min(dp[v][a][0] + dp[to][b][0])$$$ and $$$dp[v][a+b][1] = min(dp[v][a][1] + dp[to][b][0], dp[v][a][0] + dp[to][b][1])$$$.

This seems to be like a (min,+) convolution, which can be solved faster in this case since the $$$dp$$$ is convex, similary to this other problem, by mainting the difference $$$dp[v][a] - dp[v][a-1]$$$ and using small to large to merge this difference arrays.

is this the same as this problem? group link. it's was copied from some OI competitions.