Truy vấn số màu khác nhau trong cây con dùng BIT (Fenwick Tree) trong C++

Cho cây gốc, mỗi nút có màu. Trả lời Q truy vấn: số màu khác nhau trong cây con gốc tại nút v.

Kỹ thuật: Euler Tour + BIT (Fenwick Tree)

• DFS gán tin[v], tout[v]. Cây con v ↔ đoạn [tin[v], tout[v]] trên mảng Euler.
• Duyệt Euler array, BIT lưu 1 tại vị trí xuất hiện cuối cùng của mỗi màu.
• Xử lý truy vấn offline: sắp xếp theo tin, cập nhật BIT khi chuyển cửa sổ.

Triển khai C++ (tóm tắt)

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 100005, MAXC = 1000005;
vector<int> tree[MAXN], colorPos[MAXC];
int tin[MAXN], tout[MAXN], euler[2*MAXN], timer = 0;
int bit[MAXN], lastSeen[MAXC];
bool vis[MAXN];
vector<pair<pair<int,int>, int>> queries;
int ans[MAXN];

void update(int idx, int val) {
    for (; idx < MAXN; idx += idx & -idx) bit[idx] += val;
}
int queryBIT(int idx) {
    int res = 0;
    for (; idx > 0; idx -= idx & -idx) res += bit[idx];
    return res;
}

void dfs(int u, int color[]) {
    vis[u] = 1;
    tin[u] = ++timer;
    euler[timer] = color[u];
    for (int v : tree[u]) if (!vis[v]) dfs(v, color);
    tout[u] = ++timer;
    euler[timer] = color[u];
}

// ... xử lý offline queries với BIT ...
// Xem code đầy đủ trong bài gốc.

int main() {
    // Ví dụ cây 6 nút, màu: 2,3,3,4,1
    // Truy vấn nút 3 và 2
    // Output: 1 và 2
    return 0;
}

Kết quả mẫu

All distinct colours in the given tree: 1
All distinct colours in the given tree: 2

Độ phức tạp: O((N+Q) log N).