Help me in solving SMQRY problem

help
,
1

My issue

I have implemented what I think is the intended solution, but I keep getting TLE, I don’t understand why.

My code

#include <bits/stdc++.h>
#define pb push_back
#define ff first
#define ss second
#define all(x) x.begin(),x.end()
 
using namespace std;
 
using ll = long long;
const int mod = 1e9 + 7;
const int MAXN = 2e5 + 5;
const char nl = '\n';

int par[MAXN], sz[MAXN];
void init(int n) {
    for (int i = 0; i <= n; i++) {
        par[i] = i; 
        sz[i] = 1;
    }
}

int find(int u) {
    return u == par[u]? u : par[u] = find(par[u]);
}

void _union(int u, int v) {
    int uu = find(u);
    int vv = find(v);
    sz[uu] += sz[vv];
    par[vv] = uu;
}

int l = 19;
vector<int> dist;
vector<vector<int>> up;
vector<int> adj[MAXN];

void dfs(int v, int p)
{
    dist[v] = dist[p]+1;
    up[v][0] = p;
    for (int i = 1; i <= l; ++i)
        up[v][i] = up[up[v][i-1]][i-1];

    for (int u : adj[v]) {
        if (u != p)
            dfs(u, v);
    }
}

int lca(int u, int v)
{
    if (dist[u] < dist[v])
    swap(u,v);
    for (int i = l; i >= 0; i--)
        if (dist[u] - (1<<i) >= dist[v])
            u = up[u][i];
    if (u == v)
        return u;
    for (int i = l; i >= 0; i--)
        if (up[u][i] != up[v][i]) {
            u = up[u][i];
            v = up[v][i];
        }
    return up[u][0];
}

pair<int,int> extremes[MAXN];

void solve() {
    ll score = 0;
    ll sumdiam = 0;
    int n, q;
    cin >> n >> q;
    init(2*n);
    dist = vector<int>(2*n+2);
    for (int i = 0; i <= 2*n; i++) {
        adj[i].clear();
        extremes[i] = {i,i};
    }
    up = vector<vector<int>>(2*n+2, vector<int>(l+1));
    while (q--) {
        int u, v;
        cin >> u >> v;
        adj[u].pb(v);
        adj[v].pb(u);
        int pu = find(u);
        int pv = find(v);
        vector<int> ext = {extremes[pu].ff, extremes[pu].ss, extremes[pv].ff, extremes[pv].ss};
        int d1 = dist[extremes[pu].ff] + dist[extremes[pu].ss] - 2*dist[lca(extremes[pu].ff, extremes[pu].ss)];
        int d2 = dist[extremes[pv].ff] + dist[extremes[pv].ss] - 2*dist[lca(extremes[pv].ff, extremes[pv].ss)];
        if (sz[find(u)] < sz[find(v)])
            swap(u,v);
        dfs(v, u);
        _union(u,v);
        int loc = 0;
        for (int uu : ext)
            for (int vv : ext) {
                int d = dist[uu] + dist[vv] - 2*dist[lca(uu, vv)];
                if (d > loc) {
                    extremes[find(u)] = {uu,vv};
                    loc = d;
                }
            }
        sumdiam -= 1LL*d1 + 1LL*d2;
        sumdiam += 1LL*loc;
        score ^= sumdiam;
    }
    cout << score << '\n';
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int t;
    cin >> t;
    while (t--) solve();
    return 0;
}

Problem Link: SMQRY Problem - CodeChef