Cây Steiner $T[S]$ của một cây $T=(V,E)$ là cây con nhỏ nhất của $T$ chứa tất cả các đỉnh trong $S \subseteq V$.
Trong bài toán này, ta được cho một cây $T = (V, E)$. Nhiệm vụ của chúng ta là:
Khi có một tập các đỉnh đặc biệt $S \subseteq V$, trả lời câu hỏi: số cạnh của $T[S]$ là bao nhiêu?
Nếu chúng ta có một cây Steiner $T[S]$ và các đỉnh theo thứ tự Euler tour của nó là $\mathcal E(T[S]) = [v_0, v_1, \dots, v_{n-1}]$, thì:
$$\sum_{i=0}^{n-1} \text{dist}(v_i, v_{i+1 \bmod n}) = 2|E(T[S])|$$
Nói cách khác, để đi hết Euler tour, ta cần đi qua mỗi cạnh đúng hai lần.
Điều này có nghĩa là chúng ta chỉ cần quan tâm đến khoảng cách giữa các đỉnh khi cập nhật màu của một đỉnh.
Để làm việc này một cách hiệu quả, ta có thể duy trì thứ tự Euler tour của tập các đỉnh đặc biệt
$S$. Một cách đơn giản là dùng `std::set` với custom comparator dựa trên thứ tự vào (`in[]`) của DFS:
```cpp
// Ở đây dùng hàm bình thường cũng được
auto cmp = [&](int u, int v) { return in[u] < in[v]; };
set<int, decltype(cmp)> verts(cmp);
```
Giờ chúng ta có thể dễ dàng tìm đỉnh trước/đỉnh sau của một đỉnh $v$ trong $\mathcal E(S)$.
Việc còn lại là cập nhật giá trị `answer` bằng cách sử dụng:
$$\text{dist}(\text{prev}(v), v), \quad \text{dist}(v, \text{next}(v)), \quad \text{và} \quad \text{dist}(\text{prev}(v), \text{next}(v))$$
imsuck
Created at
0 likes