CF Step
Youtube Linkedin Discord Toggle Dark/Light/Auto mode Toggle Dark/Light/Auto mode Toggle Dark/Light/Auto mode Back to homepage

Hints: Sasha and a Walk in the City

The problem statement can be simplified as:

Given a tree, you need to color each node in black or white. How many colorings exist such that the path between any two vertices contains atmost 2 black vertices.

You can submit the simplified version here.

Bijection between Connected Induced Subgraphs and Valid Colorings

Recall the problem of counting the number of connected induced subgraphs of a tree.

It can be shown that there is a bijection between them.

Given a connected induced subgraph, what is the size of the minimal set of vertices required to uniquely construct this subgraph. Not just the size, the minimal set of vertices required is also fixed. Can you figure out what those are?

The leaf vertices (or to be more precise, the degree-1 vertices) are absolutely critical in determining uniqueness. This is because, if you lose track of leaf vertices, the remaining subgraph would still be connected, and you would not be able to figure out if the leaf vertex is supposed to be there or not.

Once you have all the leaf vertices, you can make the subgraph connected by adding all the vertices that lie on the path between these leaf vertices.

The minimum size required to reconstruct this subgraph is equal to the number of degree-1 vertices.

In fact, the collection of all degree-1 vertices is the minimal set required for unique construction of the subgraph.

Given a connected induced subgraph, figure out a unique coloring strategy that avoids a path containing more than 2 black vertices.
Color all the degree-1 vertices of this subgraph in black and the rest of the vertices in white. Note that that all other vertices except the degree-1 vertices were added to the subgraph only because it was on a path between 2 vertices. Hence, if we color those black, the path would now contain 3 black vertices.
Given a coloring, figure out a strategy to uniquely construct a connected induced subgraph.

Treat all the black vertices as degree-1 vertices and then expand the set to make it connected.

Why is such a construction always possible? We just need to prove that the set of black vertices represent a set of minimal leaf vertices.

A set does not contain minimal leaf vertices if it has u, v and w such that w lies on the path between u to v. However, this is not possible in our case, since this was a valid coloring, so the path cannot contain 3 black vertices.

Hence, the problem can be solved by just counting the number of connected induced subgraphs, for which I have written a blog