# Help me in solving SMQRY problem

### 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;

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++) {
extremes[i] = {i,i};
}
up = vector<vector<int>>(2*n+2, vector<int>(l+1));
while (q--) {
int u, v;
cin >> u >> v;
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