Question on Inclusion Exclusion On DP on tree Generalised?

Правка en1, от theoneandonlytron, 2026-11-12 04:52:36

Let's say I want to use DP to group nodes in a graph. I can't directly use tree DP because the graph contains cycles. But what if, by assuming that node $$$i$$$ is grouped with node $$$j$$$ in some way, I can break a cycle and then apply tree DP?

What if the graph has many cycles? Technically, I could try all possibilities in $$$2^n$$$, but is there a blog or generalization of this idea, or a problem that uses it?

One example is this USACO problem, but it only has one cycle per connected component because it is a functional graph.

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en1 Английский theoneandonlytron 2026-11-12 04:52:36 647 Initial revision (published)