Editorial for Phân chia cây

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Author: Yunan

Với mỗi đường đi $v_1,v_2,...,v_k$ ~v_1,v_2,...,v_k~, có tối đa $1$ ~1~ đỉnh lá của cây, khi đó đỉnh lá chỉ có thể nằm ở vị trí cuối cùng của đường đi $($ ~(~tương ứng đỉnh $v_k)$ ~v_k)~. Ngoài ra, mỗi đỉnh lá thuộc chính xác một đường đi. Vì vậy, đáp án bài toán là số đỉnh lá $($ ~(~ngoại trừ đỉnh gốc $)$ ~)~ của cây.

Độ phức tạp: $O(N)$ ~O(N)~

Editorial for Phân chia cây

Comments