题目:P3302 [SDOI2013] 森林

错误代码：

#include<bits/stdc++.h>
#define M 80005

using namespace std;

int m, n, len, rt[M], node_cnt, lastans, testcase, t;
int bin[31], lg[M], a[M], b[M], ls[M << 9], rs[M << 9], sum[M << 9], fa[M][31], deep[M], size[M];
vector<int> edge[M];
char ch;

void update_single(int &new_id, int pre, int l, int r, int pos) {
    new_id = ++ node_cnt;
    ls[new_id] = ls[pre];
    rs[new_id] = rs[pre];
    sum[new_id] = sum[pre] + 1;
    if(l == r)
        return;
    int mid = (l + r) >> 1;
    if(pos <= mid)
        update_single(ls[new_id], ls[pre], l, mid, pos);
    else
        update_single(rs[new_id], rs[pre], mid + 1, r, pos);
}

int ask(int l, int r, int x, int y, int lca, int f_lca, int k) {
    if(l == r)
        return l;
    int mid = (l + r) >> 1, op = sum[ls[x]] + sum[ls[y]] - sum[ls[lca]] - sum[ls[f_lca]];
    if(op >= k)
        return ask(l, mid, ls[x], ls[y], ls[lca], ls[f_lca], k);
    else
        return ask(mid + 1, r, rs[x], rs[y], rs[lca], rs[f_lca], k - op);
}

void dfs(int u, int fu) {
    fa[u][0] = fu;
    size[u] = 1;
    deep[u] = deep[fu] + 1;
    for(int i = 1; i <= lg[deep[u]]; ++ i)
        fa[u][i] = fa[fa[u][i - 1]][i - 1];
    update_single(rt[u], rt[fa[u][0]], 1, len, a[u]);
//    cout << u << ' ' << fa[u][0] << " " << rt[u] << endl;
    for(int i = 0; i < edge[u].size(); ++ i)
        if(edge[u][i] != fu)
            dfs(edge[u][i], u);
    if(fu)
        size[fu] += size[u];
}

inline int LCA(int x, int y) {
    int v = deep[x] - deep[y];
    if(v < 0) {
        v = -v;
        swap(x, y);
    }
    while(v)
        for(int i = lg[deep[x] - deep[y]]; v; -- i)
            if(v >= bin[i])
                x = fa[x][i], v -= bin[i];
    if(x == y)
        return x;
    for(int i = lg[deep[x]]; i >= 0; -- i)
        if(fa[x][i] != fa[y][i])
            x = fa[x][i], y = fa[y][i];
    return fa[x][0];
}

void Marge(int x, int y) {
    if(size[y] > size[x])
        swap(x, y);
    edge[x].push_back(y);
    edge[y].push_back(x);
    dfs(y, x);
    int ji = size[y];
    for(int i = fa[x][0]; i; i = fa[i][0])
    	size[i] += ji;
}

signed main() {
//	freopen("P3302_2.in", "r", stdin);
//	freopen("out.out", "w", stdout);
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    cin >> testcase >> n >> m >> t;
    bin[0] = 1;
    for(int i = 1; i <= 30; ++ i)
        bin[i] = bin[i - 1] << 1;
    lg[2] = 1;
    for(int i = 3; i <= n; ++ i)
        lg[i] = lg[i >> 1] + 1;
    for(int i = 1; i <= n; ++ i) {
        cin >> a[i];
        b[i] = a[i];
    }
    stable_sort(b + 1, b + 1 + n);
    len = unique(b + 1, b + 1 + n) - b - 1;
    for(int i = 1; i <= n; ++ i)
		a[i] = lower_bound(b + 1, b + 1 + n, a[i]) - b; 
    for(int i = 1; i <= m; ++ i) {
        int u, v;
        cin >> u >> v;
        edge[u].push_back(v);
        edge[v].push_back(u);
    }
    for(int i = 1; i <= n; ++ i)
        if(!fa[i][0])
            dfs(i, 0);
    for(int i = 1; i <= t; ++ i) {
        cin >> ch;
        if(ch == 'Q') {
            int x, y, k;
            cin >> x >> y >> k;
            x = x ^ lastans;
            y = y ^ lastans;
            k = k ^ lastans;
            int lca = LCA(x, y);
//            cout << x << " " << y << " " << lca << " " << fa[lca][0] << endl;
//            cout << rt[x] << " " << rt[y] << " " << rt[lca] << " " << rt[fa[lca][0]] << endl;
            lastans = ask(1, len, rt[x], rt[y], rt[lca], rt[fa[lca][0]], k);
//            cout << lastans << endl;
            lastans = b[lastans];
            cout << lastans << endl;
        }
        else {
            int x, y;
            cin >> x >> y;
            x = x ^ lastans;
            y = y ^ lastans;
//            cout << x << " " << y << endl;
            Marge(x, y);
        }
    }
}

将函数 $dfs$ 里的

    for(int i = 1; i <= lg[deep[u]]; ++ i)

改成

    for(int i = 1; i <= 16; ++ i)

就能对，但蒟蒻并不知道为什么。

蒟蒻自认为在加边（$Merge$）过程中 $deep$ 数组更新的很彻底，但好像还是有问题。

求大佬解答 qwq