CF1926G Vlad and Trouble at MIT

Vladislav has a son who really wanted to go to MIT. The college dormitory at MIT (Moldova Institute of Technology) can be represented as a tree with $ n $ vertices, each vertex being a room with exactly one student. A tree is a connected undirected graph with $ n $ vertices and $ n-1 $ edges. Tonight, there are three types of students: - students who want to party and play music (marked with $ \texttt{P} $ ), - students who wish to sleep and enjoy silence (marked with $ \texttt{S} $ ), and - students who don't care (marked with $ \texttt{C} $ ). Initially, all the edges are thin walls which allow music to pass through, so when a partying student puts music on, it will be heard in every room. However, we can place some thick walls on any edges — thick walls don't allow music to pass through them. The university wants to install some thick walls so that every partying student can play music, and no sleepy student can hear it. Because the university lost a lot of money in a naming rights lawsuit, they ask you to find the minimum number of thick walls they will need to use.

N/A

N/A

In the first case, we can install one thick wall between rooms $ 1 $ and $ 2 $ , as shown below. We cannot install $ 0 $ walls, since then the music from room 3 will reach room 2 where a student wants to sleep, so the answer is $ 1 $ . There are other valid solutions.