# 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.

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.

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