Hướng giải của Kích thước vương quốc

Nhớ rằng hướng dẫn giải này chỉ nên sử dụng khi bế tắc, và tuyệt đối không nên sao chép mã nguồn kèm theo. Hãy tôn trọng tác giả bài tập và người viết hướng dẫn giải.
Nộp mã nguồn lời giải chính thức trước khi giải bài tập đó có thể khiến bạn bị ban.

Tác giả: kienadmin

Nhận xét

Bài toán yêu cầu tính kích thước subtree của một đỉnh trên cây. Với mỗi truy vấn, nếu ta duyệt DFS và đếm số đỉnh trong subtree thì độ phức tạp là \(O(NQ)\), không đủ nhanh.

Ý tưởng giải

Sử dụng kỹ thuật Euler Tour (DFS flatten) để biến cây thành mảng tuyến tính:

  1. Thực hiện DFS từ gốc (đỉnh 1), ghi lại thời điểm vào \(tin[u]\) và thời điểm ra \(tout[u]\) cho mỗi đỉnh.
  2. Tính chất quan trọng: Tất cả đỉnh trong subtree của \(u\) tạo thành đoạn liên tục \([tin[u], tout[u]]\) trên mảng Euler Tour.
  3. Kích thước subtree của \(u\) = \(tout[u] - tin[u] + 1\).

Độ phức tạp

  • Tiền xử lý DFS: \(O(N)\)
  • Mỗi truy vấn: \(O(1)\)
  • Tổng: \(O(N + Q)\)

Code mẫu

// Giải thuật ett cho bài toán ett-size\n#include <bits/stdc++.h>
using namespace std;

const int MAXN = 200005;
vector<int> adj[MAXN];
int tin[MAXN], tout[MAXN];
int timer_dfs = 0;

void dfs(int u, int parent) {
    tin[u] = ++timer_dfs;
    for (int v : adj[u]) {
        if (v != parent) {
            dfs(v, u);
        }
    }
    tout[u] = timer_dfs;
}

int main() {
    // Doc du lieu dau vao
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, q;
    cin >> n >> q;

    for (int i = 0; i < n - 1; i++) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    // DFS de tinh tin va tout
    dfs(1, 0);

    while (q--) {
        int u;
        cin >> u;
        // Kich thuoc subtree = tout - tin + 1
        cout << tout[u] - tin[u] + 1 << "\n";
    }
    return 0;
}

Nhận xét

Không có ý kiến tại thời điểm này.