Tóm tắt đề bài

Cho đồ thị \(n\) đỉnh ban đầu không có cạnh. Ta thực hiện \(n-1\) thao tác thêm cạnh, mỗi thao tác thêm một cạnh nối hai đỉnh \(u\) và \(v\) sao cho đồ thị luôn duy trì cấu trúc rừng (các thành phần liên thông là cây). Có hai loại thao tác:

• Loại 1: \(u = x \oplus res, v = y \oplus res\).
• Loại 2: \(u = x, v = y\).

Sau mỗi thao tác, tính \(sum\_dia\) là tổng độ dài đường kính của tất cả các cây trong rừng hiện tại. Sau đó cập nhật \(res = res \oplus sum\_dia\). In ra giá trị \(res\) sau mỗi bước.

Phân tích

• Số lượng đỉnh: \(n \le 2 \cdot 10^5\).
• Số lượng thao tác: \(n-1\).
• Đặc điểm: Khi thêm một cạnh nối hai cây khác nhau, chúng sẽ hợp nhất thành một cây duy nhất. Chúng ta cần cập nhật đường kính của cây mới một cách hiệu quả.
• Tính chất đường kính: Nếu ta nối hai cây \(T_1\) và \(T_2\) bằng một cạnh \((u, v)\) với \(u \in T_1\) và \(v \in T_2\), đường kính của cây mới sẽ là giá trị lớn nhất trong các giá trị sau:
  1. Đường kính của \(T_1\).
  2. Đường kính của \(T_2\).
  3. Khoảng cách lớn nhất từ \(u\) trong \(T_1\) + 1 + khoảng cách lớn nhất từ \(v\) trong \(T_2\).
• Khoảng cách: Để tính khoảng cách giữa hai đỉnh trong cây, ta sử dụng công thức: \(dist(u, v) = depth(u) + depth(v) - 2 \cdot depth(LCA(u, v))\).

Hướng giải quyết

1. Quản lý các thành phần liên thông

Sử dụng cấu trúc dữ liệu DSU (Disjoint Set Union) để quản lý các thành phần liên thông. Với mỗi thành phần, ta lưu trữ:

• Hai đầu mút của đường kính hiện tại: \(diaA\) và \(diaB\).
• Độ dài đường kính: \(diaLen\).

2. Cập nhật đường kính khi hợp nhất

Khi nối cạnh \((u, v)\), cây mới sẽ có đường kính mới. Hai đầu mút của đường kính mới chắc chắn sẽ nằm trong tập hợp \(\{diaA_1, diaB_1, diaA_2, diaB_2\}\). Tuy nhiên, do ta nối cạnh cụ thể \((u, v)\), ta có thể tính nhanh hơn:

• Ứng viên đường kính mới có thể là đường kính cũ của \(T_1\) hoặc \(T_2\).
• Hoặc là đường đi đi qua cạnh \((u, v)\), có độ dài: \(\max(dist(u, diaA_1), dist(u, diaB_1)) + 1 + \max(dist(v, diaA_2), dist(v, diaB_2))\).

3. Kỹ thuật Small-to-Large và Cập nhật LCA

Vấn đề khó nhất là đồ thị thay đổi (thêm cạnh), làm thay đổi cấu trúc cây và ảnh hưởng đến việc tính \(LCA\).

• Ta sử dụng kỹ thuật Small-to-Large merging: Luôn gộp cây có kích thước nhỏ hơn vào cây có kích thước lớn hơn.
• Khi gộp cây nhỏ \(T_{small}\) vào \(T_{large}\) thông qua cạnh \((u, v)\), ta coi \(v\) là cha của \(u\). Sau đó, ta thực hiện duyệt toàn bộ các đỉnh trong \(T_{small}\) để cập nhật lại:
  • Mảng up[node][k] (Binary Lifting) phục vụ tính LCA.
  • Độ sâu depthArr[node].
  • Thành phần liên thông hiện tại.
• Tổng độ phức tạp của việc duyệt và cập nhật này là \(O(n \log^2 n)\) vì mỗi đỉnh chỉ bị "gộp" tối đa \(\log n\) lần.

4. Các bước thực hiện

1. Khởi tạo \(n\) thành phần liên thông, mỗi đỉnh là một cây có đường kính bằng 0.
2. Với mỗi truy vấn:
   • Giải mã \(u, v\) nếu là loại 1.
   • Tìm đại diện \(ru, rv\) của hai cây chứa \(u, v\).
   • Tính đường kính mới của cây sau khi gộp.
   • Cập nhật \(sum\_dia = sum\_dia - diaLen[ru] - diaLen[rv] + new\_len\).
   • Thực hiện gộp cây nhỏ vào cây lớn, cập nhật lại thông tin LCA cho các đỉnh ở cây nhỏ.
   • Tính \(res = res \oplus sum\_dia\) và in ra.

Độ phức tạp

• Thời gian: \(O(n \log^2 n)\) do kỹ thuật gộp cây nhỏ vào cây lớn kết hợp với Binary Lifting để tìm LCA.
• Bộ nhớ: \(O(n \log n)\) để lưu bảng Binary Lifting.

Code tham khảo

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

const int MAXN = 200005;
const int LOG = 19;

int n;
vector<int> adj[MAXN];
int dsu[MAXN], sz[MAXN], comp_id[MAXN];
int up[MAXN][LOG], depthArr[MAXN];
int diaA[MAXN], diaB[MAXN], diaLen[MAXN];
vector<int> comp_nodes[MAXN];

int findp(int x) {
    return dsu[x] == x ? x : dsu[x] = findp(dsu[x]);
}

int get_lca(int u, int v) {
    if (depthArr[u] < depthArr[v]) swap(u, v);
    for (int k = LOG - 1; k >= 0; k--) {
        if (up[u][k] != -1 && depthArr[up[u][k]] >= depthArr[v])
            u = up[u][k];
    }
    if (u == v) return u;
    for (int k = LOG - 1; k >= 0; k--) {
        if (up[u][k] != up[v][k]) {
            u = up[u][k];
            v = up[v][k];
        }
    }
    return up[u][0];
}

int dist(int u, int v) {
    return depthArr[u] + depthArr[v] - 2 * depthArr[get_lca(u, v)];
}

void update_node(int u, int p, int d) {
    up[u][0] = p;
    depthArr[u] = d;
    for (int k = 1; k < LOG; k++) {
        if (up[u][k - 1] != -1) up[u][k] = up[up[u][k - 1]][k - 1];
        else up[u][k] = -1;
    }
}

int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr);
    cin >> n;
    for (int i = 1; i <= n; i++) {
        dsu[i] = i; sz[i] = 1; comp_id[i] = i;
        comp_nodes[i].push_back(i);
        diaA[i] = diaB[i] = i; diaLen[i] = 0;
        for (int k = 0; k < LOG; k++) up[i][k] = -1;
    }

    ll sum_dia = 0, res = 0;
    for (int i = 0; i < n - 1; i++) {
        int t, x, y; cin >> t >> x >> y;
        int u = (t == 1) ? (x ^ res) : x;
        int v = (t == 1) ? (y ^ res) : y;

        adj[u].push_back(v); adj[v].push_back(u);
        int ru = findp(u), rv = findp(v);
        if (sz[ru] > sz[rv]) { swap(ru, rv); swap(u, v); }

        sum_dia -= diaLen[ru]; sum_dia -= diaLen[rv];

        // Tính đường kính mới
        int d1 = dist(u, diaA[ru]), d2 = dist(u, diaB[ru]);
        int d3 = dist(v, diaA[rv]), d4 = dist(v, diaB[rv]);
        int cand_len = max(d1, d2) + 1 + max(d3, d4);
        int new_len = max({diaLen[ru], diaLen[rv], cand_len});

        int nA, nB;
        if (new_len == diaLen[ru]) { nA = diaA[ru]; nB = diaB[ru]; }
        else if (new_len == diaLen[rv]) { nA = diaA[rv]; nB = diaB[rv]; }
        else {
            nA = (d1 >= d2) ? diaA[ru] : diaB[ru];
            nB = (d3 >= d4) ? diaA[rv] : diaB[rv];
        }

        // Gộp cây nhỏ ru vào rv (u nối với v)
        update_node(u, v, depthArr[v] + 1);
        vector<int> q = {u};
        int head = 0;
        while(head < q.size()){
            int curr = q[head++];
            for(int next_v : adj[curr]){
                if(findp(next_v) == ru && next_v != up[curr][0]){
                    update_node(next_v, curr, depthArr[curr] + 1);
                    q.push_back(next_v);
                }
            }
        }

        for(int node : q) comp_nodes[rv].push_back(node);
        comp_nodes[ru].clear();
        dsu[ru] = rv; sz[rv] += sz[ru];
        diaA[rv] = nA; diaB[rv] = nB; diaLen[rv] = new_len;
        sum_dia += new_len;
        res ^= sum_dia;
        cout << res << "\n";
    }
    return 0;
}