adaptatron's blog

By adaptatron, 4 months ago, In English

The editorial for ABC340G: Leaf Color from last Atcoder Beginner Contest mentions an interesting exercise/subproblem for the readers

Fix a color and find the answer in $$$O(N)$$$ with Tree DP. Although not easy, it is a good exercise for blue coders, so we recommend you to think about it.

So I created a blog post that discusses how to find

  1. The number of induced subgraphs that are trees.
  2. Number of connected induced subgraphs with degree $$$d$$$ for any $$$d$$$.
  3. Number of connected induced subgraphs with degrees $$$0$$$, $$$1$$$ and $$$\geq 2$$$.
  4. Number of connected induced subgraphs with monochromatic degree 1 vertices.
  5. Followup problem to apply the concepts learned.

To help you solidify the concepts discussed, I've created 2 + 1 practice problems. You can access them here: https://mirror.codeforces.com/group/7Dn3ObOpau/contest/504547

https://cfstep.com/training/tutorials/trees/dp-on-induced-subgraphs-of-a-tree/

If you have an alternate solution for any of these problems, do let me know in the comments.

The problems are untested. If you see any issues, please let me know.

If you need any help or hints for the practice problem, you can ask on my Discord Server or on the Twitter thread. In case you are interested, you can also checkout my youtube channel

  • Vote: I like it
  • +12
  • Vote: I do not like it