Solutions of Mushroom harvesting

Select solution language

menkh Created at 4 likes

Ta sẽ dùng Euler Tour để trải phẳng cây ra. Gọi $t[]$ là mảng biểu diễn đường đi Euler của cây. Gọi $in[u]$ và $out[u]$ lần lượt là vị trí đầu tiên và vị trí cuối cùng nhất trong $t$ của đỉnh $u$. Trong $t$, mọi đỉnh thuộc cây con gốc $u$ đều nằm liên tiếp từ vị trí $in[u]$ đến $out[u]$. Đồng thời đỉnh $v$ thuộc cây con gốc $u$ khi và chỉ khi $in[u] \le in[v] \le out[v] \le out[u]$. Vậy khi đã hái nấm ở đỉnh $u$, ta chỉ việc đánh dấu lại đoạn $\[in[u], out[u]\]$, và ở ngày $i$, nếu muốn biết có bao nhiêu đỉnh đã tới để hái nấm ở các ngày trước, ta chỉ việc tính tổng đoạn $\[1, in[a_i]\]$, tương ứng với việc đếm các đỉnh đã đánh dấu trên đường đi từ 1 tới đỉnh $a_i$ Các thao tác trên có thể được thực hiện bằng Segment Tree + Lazy update hoặc đơn giản hơn là dùng Fenwick Tree (BIT).