Solutions of Library

Select solution language

TENJOKE Created at 1 likes

Ta có **nhánh** là các nhánh khác nhau phân ra từ đỉnh $1$. Gọi $\min(x, y)$ là cái cạnh nhỏ nhất trên đường đi từ $x \rightarrow y$. Đầu tiên mình phải phân ra là mỗi đỉnh ở nhánh thứ mấy, sort truy vấn theo nhánh. Với từng nhánh kiếm LCA (tạm gọi là $\text{belan}$) của tất cả các đỉnh trong nhánh. Mình sẽ chắn một tấm duy nhất là $\min(\text{belan}, 1)$ hoặc nhiều tấm là $\sum \min(x(i), \text{belan})$ với $x(i)$ là mỗi đỉnh thuộc nhánh, cái nào nhỏ hơn thì mình lấy: $$ \text{ans} += \min(\min(\text{belan}, 1), \sum \min(x(i), \text{belan})) $$ Trường hợp đặc biệt là nếu có một cái $x(i) == \text{belan}$ thì mình sẽ lấy luôn là $$ \text{ans} += \min(\text{belan}, 1) $$ **:)** **Chúc các bạn thành công !**