Hi, I made a graph problem that I couldn't solve and I was wondering if it's solvable at all, so I'd appreciate if someone solved it (doesn't have to be solvable in the given constraints just any solution).
given a rooted weighted tree made of $$$n$$$ nodes you start from the root and go to any adjacent node you are given $$$m$$$ resturants each one will be on a node you are required to print the minimum cost to visit $$$k$$$ different resturants (you can visit an edge more than once)
$$$1\le n \le 10^5$$$, $$$m \le n$$$, $$$k \le m$$$, $$$1 \le cost \le 10^9$$$
Do we need to return to the root after visiting $$$k$$$ restaurants?
no
الراجل ده بيتكلم صح
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:
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.
You have to visit k different black nodes can't be the same node and visit it k number of times.
Ok, I misunderstood it, although the statement does not say anything about it.
Yeah sorry my bad I will edit the statement.
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?
yes
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.
so k is the number of restaurants that I will pick in the subtree right?
Yes
Thank you so much, I think I understand your solution <3
Actually, not sure if this is convex... It still should solve in $$$O(N^2)$$$...
is this the same as this problem? group link. it's was copied from some OI competitions.
It is similar but this one is rooted so you have to visit some edges multiple times to achieve an answer
unrooted seems to be harder than rooted, and also in that problem you can pass through an edge multiple times
It's not about which is the harder version it's a totally different solution, the problem was solved in a comment above if you want to see the solution