Đề bài gốc: BOI 2019 - Valley

Tóm tắt đề: Cho một cây $N$ đỉnh, các cạnh có trọng số. Cây có 1 đỉnh thoát $S$ và $P$ đỉnh đặc biệt. Bạn cần trả lời $Q$ câu hỏi có dạng:

• Nếu bỏ cạnh $I$ khỏi cây, thì có đường đi từ $T$ đến $S$ hay không?
• Nếu không có, đỉnh đặc biệt gần $T$ nhất có khoảng cách là bao nhiêu?

Subtask 1: ~1 \le N ≤ 100, 1 ≤ Q ≤ 10\,000~, đồ thị có dạng 1-2-3-...-N

Bỏ một cạnh $(u, u+1)$ bất kì sẽ tách đồ thị thành hai phía: 1-2-...-u và (u+1)-(u+2)-...N. Ta có thể dễ dàng kiểm tra $T$ và và $S$ có thuộc cùng một phía hay không. Nếu không, ta sẽ duyệt qua phần đồ thị chứa $T$ để xác định khoảng cách đỉnh đặc biệt gần nhất với $T$.

Subtask 2: ~1 ≤ N ≤ 1\,000, 1 ≤ Q ≤ 1\,000~

Với subtask này, ta thực hiện những gì đề bài yêu cầu. Với mỗi câu hỏi, ta thực hiện BFS từ $T$ để xác định $T$ và $S$ có liên thông với nhau hay không, nếu không, duyệt danh sách các đỉnh đặc biệt xem khoảng cách ngắn nhất đến $T$ là bao nhiêu.

Subtask 3: ~1 ≤ N ≤ 100\,000, 1 ≤ Q ≤ 100\,000~, và mọi đỉnh đều là đỉnh đặc biệt

Với subtask này, do mọi đỉnh đều là đỉnh đặc biệt, nên nếu $T$ và $S$ không liên thông, ta chỉ cần in ra khoảng cách $0$. Việc còn lại là ta cần tìm cách kiểm tra tính liên thông giữa $T$ và $S$ đủ nhanh để đáp ứng giới hạn của subtask này.

Chọn $S$ là gốc của cây, ta tiến hành DFS cây từ $S$, ta dùng kĩ thuật đường đi Euler trên cây để lưu lại các thời điểm bắt đầu thăm ~t_{in}~ và thăm xong ~t_{out}~ của mỗi đỉnh trên cây. Từ đó ta có thể kiểm tra xem cạnh thứ $I$ có nằm trên đường đi từ $S$ đến $T$ hay không với độ phức tạp là $O(1)$. Ta có thể kiểm tra bằng cách sử dụng tính chất sau: Nếu $v$ là con của $u$, thì điều kiện sau thỏa mãn: $$ t_{in}(u) \le t_{in}(v) \le t_{out}(v) \le t_{out}(u) $$

Subtask 4: ~1 ≤ N ≤ 100\,000, 1 ≤ Q ≤ 100\,000~.

Với subtask 3, ta đã biết cách kiểm tra trường hợp in ra failed. Đến subtask 4, ta sẽ tìm cách giải quyết trường hợp còn lại của bài toán. Xét truy vấn $(I, T)$, gọi $p$ là đỉnh thấp hơn thuộc cạnh $I$. Ta cần tìm đỉnh đặc biệt $v$ thuộc cây con gốc $p$ sao cho có khoảng cách đến $T$ là ngắn nhất.

Gọi $lca(u, v)$ là tổ tiên chung thấp nhất của hai đỉnh $u$ và $v$. Khi đó, độ dài đường đi từ $u$ đến $v$ được xác định bằng công thức. $$ dist_{S}[u] + dist_{S}[v] - 2\times dist_{S}[lca(u, v)] $$

Để tìm đỉnh đặc biệt gần $T$ nhất, ta gọi $u$ là đỉnh cần tìm, giả sử ta biết $lca(u, T)$ là $w$. Khi đó, đáp án của truy vấn là $$ dist_{S}[T] + \min\limits_{v \ \in \text{ subtree}(w)}dist_{S}[v] - 2\times dist_{S}[w] $$

Có thể thấy rằng cụm ~\min\limits_{v \ \in \text{ subtree}(w)}dist_{S}[v] - 2\times dist_{S}[w]~ không phụ thuộc vào $T$ và có thể được chuẩn bị trước, ta gọi $best[w]$ sao cho: $$ best[w] = \min\limits_{v \ \in \text{ subtree}(w)}dist_{S}[v] - 2\times dist_{S}[w] $$

Khi đó $best[w]$ có thể được chuẩn bị trước bằng quy hoạch động như sau:

1. DFS để tìm ~\min\limits_{v \ \in \text{ subtree}(w)}dist_{S}[v]~ và lưu vào $best[w]$. Độ phức tạp $O(N)$.
2. Với mỗi đỉnh $w$, thêm ~- 2\times dist_{S}[w]~ vào ~best[w]~

Như vậy, nếu biết trước $w$ là đỉnh "cao nhất" của đường đi từ $T$ đến đỉnh đặc biệt, khoảng cách của đỉnh đặc biệt gần $T$ nhất sẽ là $dist_{S}[T] + best[w]$. Đáp án cho truy vấn trở thành: $$ $dist_{S}[T] + \min\limits_{w} best[w]$ $$ với $w$ thuộc tập đỉnh nằm trên đường đi từ $T$ đến $p$.

Ta có thể tính ~\min\limits_{w} best[w]~ với $w$ từ $T$ đến $p$ trong $O(\log N)$ bằng kĩ thuật binary lifting, dùng cấu trúc dữ liệu bảng thưa. Gọi $par[u][k]$ là tổ tiên thứ $2^k$ của $u$, và $jumpBest[u][k]$ là $best[w]$ nhỏ nhất với $w$ nằm trên đường đi từ $u$ đến tổ tiên thứ $2^k - 1$ của $u$. Ta có $$ \begin{align*} par[u][0] & \text{ là cha trực tiếp của } u \\ par[u][k] &= par[par[u][k-1]][k-1]\\ jumpBest[u][0] &= best[u]\\ jumpBest[u][k] &= \min(jumpBest[u][k-1], jumpBest[par[u][k-1]][k-1]) \end{align*} $$

Như vậy, tóm tắt lời giải như sau:

1. DFS để tính các giá trị: ~t_{in}, t_{out}, best, par[u][0]~ trong $O(N)$
2. Chuẩn bị bảng thưa $par$ và $jumpBest$ trong $O(N\log N)$
3. Trả lời truy vấn, mỗi truy vấn mất $O(\log N)$. Tổng cộng $O(Q \log N)$.

Như vậy độ phức tạp của lời giải này là $\mathcal{O}((N+Q)\log N)$.

Code tham khảo

#include <iostream>
#include <vector>

using namespace std;

typedef long long ll;

const int maxn = 200005;
const int maxlg = 20;
const ll inf = 1LL << 60;

vector<pair<int, ll>> adj [maxn];
ll height [maxn];
int lvl [maxn];
ll dp [maxn];
bool store [maxn];
int start_time [maxn];
int end_time [maxn];
int cur_time;

void build_dp (int vertex, int parent, ll cur_height) {
  cur_time++;
  start_time[vertex] = cur_time;

  height[vertex] = cur_height;
  lvl[vertex] = lvl[parent] + 1;
  for (pair<int, ll> nxt : adj[vertex]) {
    if (nxt.first != parent) {
      build_dp(nxt.first, vertex, cur_height + nxt.second);
    }
  }

  if (store[vertex]) {
    dp[vertex] = height[vertex];
  } else {
    dp[vertex] = inf;
    for (pair<int, ll> nxt : adj[vertex]) {
      if (nxt.first != parent) {
        dp[vertex] = min(dp[vertex], dp[nxt.first]);
      }
    }
  }

  end_time[vertex] = cur_time;
}

bool is_parent (int u, int par) {
  return start_time[par] <= start_time[u] && end_time[u] <= end_time[par];
}

int jmp [maxn][maxlg];
ll ans_jmp [maxn][maxlg];

void build_jmp (int vertex, int parent) {
  jmp[vertex][0] = parent;
  if (dp[vertex] == inf) {
    ans_jmp[vertex][0] = inf;
  } else {
    ans_jmp[vertex][0] = dp[vertex] - 2 * height[vertex];
  }

  for (int i = 1; i < maxlg; i++) {
    jmp[vertex][i] = jmp[jmp[vertex][i - 1]][i - 1];
    ans_jmp[vertex][i] = min(ans_jmp[vertex][i - 1], ans_jmp[jmp[vertex][i - 1]][i - 1]);
  }

  for (pair<int, ll> nxt : adj[vertex]) {
    if (nxt.first != parent) {
      build_jmp(nxt.first, vertex);
    }
  }
}

ll query (int vertex, int forb) {
  if (!is_parent(vertex, forb)) {
    return -1;
  }

  ll cur_h = height[vertex];

  int diff = lvl[vertex] - lvl[forb];
  ll ans = inf;
  for (int i = maxlg - 1; i >= 0; i--) {
    if (diff & 1 << i) {
      ans = min(ans, ans_jmp[vertex][i]);
      vertex = jmp[vertex][i];
    }
  }
  ans = min(ans, ans_jmp[vertex][0]);

  if (ans != inf) {
    ans += cur_h;
  }

  return ans;
}

int main () {
  int vertexc, storec, queryc, root;
  cin >> vertexc >> storec >> queryc >> root;

  vector<pair<int, int>> edges;
  for (int i = 0; i < vertexc - 1; i++) {
    int u, v, w;
    cin >> u >> v >> w;

    adj[u].push_back(make_pair(v, w));
    adj[v].push_back(make_pair(u, w));
    edges.push_back(make_pair(u, v));
  }

  for (int i = 0; i < storec; i++) {
    int x;
    cin >> x;
    store[x] = true;
  }

  build_dp(root, root, 0);
  build_jmp(root, root);

  for (int i = 0; i < vertexc - 1; i++) {
    if (lvl[edges[i].first] < lvl[edges[i].second]) {
      swap(edges[i].first, edges[i].second);
    }
  }

  for (int i = 0; i < queryc; i++) {
    int forb_id, cur_vertex;
    cin >> forb_id >> cur_vertex;

    ll ans = query(cur_vertex, edges[forb_id - 1].first);
    if (ans == -1) {
      cout << "failed" << '\n';
    } else if (ans == inf) {
      cout << "miss" << '\n';
    } else {
      cout << ans << '\n';
    }
  }
}