Solutions of White path

Select solution language

Jorge_Slime Created at 7 likes

The approach involves performing a DFS starting from any node in the tree. During the traversal, a running count of white and black vertices is maintained. If a node is white (`0`), the counter increases by `+1`, and if it's black (`1`), the counter decreases by `-1`. This can be expressed as: ```cpp count += s[node - 1] == '0' ? 1 : -1; ``` As each node is visited, we check if the current count is positive. If it is, it means that along the path from the root to the current node, there are more white vertices than black ones, and this node qualifies. This method ensures efficient traversal in $ O(n) $, as each node is visited exactly once.

angwangsushi Created at 0 likes

# **Lưu ý: Hãy tự nghĩ cách giải, chỉ xem sol khi bí.** # **Ý TƯỞNG**: **Gọi**: $cnt[u]$: có bao nhiêu đỉnh từ đường đi *ngắn nhất* bắt đầu từ đỉnh $1$ và kết thúc ở đỉnh $u$. $white[u]$: có bao nhiêu đỉnh **màu trắng** từ đường đi *ngắn nhất* bắt đầu từ đỉnh $1$ đến đỉnh $u$. $\Rightarrow$ Tại đỉnh $u$, số lượng đỉnh màu đen (bắt đầu từ đỉnh $1$ đến đỉnh $u$) = $cnt[u] - white[u]$. Như vậy việc so sánh sẽ trở nên dễ dàng. *** Giờ thì ta chỉ cần tính trước 2 mảng $cnt$ và $white$ là được. ***Đối với mảng $cnt$:*** * Khỏi tạo $cnt[1] = 1$ * Duyệt (bfs hoặc dfs), với mỗi $(v: adj[u])$, $cnt[v] = cnt[u] + 1$. ***Đối với mảng $white$:*** * Khởi tạo : với mỗi đỉnh $u$ nếu đỉnh đó là màu trắng thì ta cho $white[u]=1$ * Duyệt (bfs hoặc dfs), với mỗi $v: adj[u]$, nếu đỉnh v là màu trắng thì $white[v] = white[u] +1$. Ngược lại $white[v] = white[u]$