DUALDIST- June Long Challenge

In DUALDIST problem when i tried bfs on both a and b in each query it was partially correct without any TLE but when I tried dfs only once for each test case it was giving me TLE can anyone please help me

My code with one dfs for each test case

``````#include <bits/stdc++.h>

using namespace std;

#define MAX 10000000

int vis[MAX];

int Euler[2 * MAX];

int eulerTreeIndex[MAX];

int eulerFirstIndex[MAX];

int lvl[MAX];

vector<int> bin_log;

map<int, vector<int>> lookup;

int nextEulerIndex;

void add_edge(int u, int v)

{

}

// Function to store Euler Tour of tree

void eulerTree(int u, int &indx, int nextLvl)

{

vis[u] = 1;

//assigning 0 to n-1 number to each value in graph

eulerTreeIndex[u] = nextEulerIndex;

eulerFirstIndex[nextEulerIndex] = indx;

lvl[nextEulerIndex] = nextLvl;

nextEulerIndex ++;

Euler[indx++] = eulerTreeIndex[u];

for (auto it : adj[u]) {

if (!vis[it]) {

eulerTree(it, indx, nextLvl+1);

Euler[indx++] = eulerTreeIndex[u];

}

}

}

// Function to print Euler Tour of tree

void printEulerTour(int root, int N, int nextLvl)

{

int index = 0;

eulerTree(root, index, nextLvl);

for (int i = 0; i < (2*N-1); i++)

cout << Euler[i] << " ";

cout<<"\n";

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

{

cout<<eulerTreeIndex[i]<<" ";

}

cout<<"\n";

for (int i = 0; i < N; i++)

{

cout<<eulerFirstIndex[i]<<" ";

}

}

void makeBinaryLog(int n){

int size = bin_log.size();

for (int i = bin_log.size(); i <= n; i++)

{

bin_log.push_back(bin_log[i/2] + 1);

}

}

void RMQmin(int n){

// int n = eularTourIndexes.size();

for (int i = 0; i < n; i++)

{

//lookup[i][0] = i

lookup[i].push_back(Euler[i]);

}

int maxPowerOf2 = bin_log[n];

for (int j = 1; j <= maxPowerOf2; j++)

{

for (int i = 0; i + (1<<j) - 1 < n; i++)

{

int minimumVal = min(lookup[i][j-1], lookup[i + (1<<(j-1))][j-1]);

lookup[i].push_back(minimumVal);

}

}

}

int lca(int a, int b){

//number with least value of eular index between first ocuurence of a and b

int leastVal;

int L = min(eulerFirstIndex[a], eulerFirstIndex[b]);

int R = max(eulerFirstIndex[a], eulerFirstIndex[b]);

int length = R - L + 1;

int k = bin_log[length];

leastVal = min(lookup[L][k], lookup[R - (1<<k) + 1][k]);

return leastVal;

}

int shortestDistance(int a, int b){

//lvla + lvlb - 2*lvl of lca

int shortestDis = lvl[a] + lvl[b] - 2 * lvl[lca(a, b)];

return shortestDis;

}

// Driver code

int main()

{

ios_base::sync_with_stdio(false);

cin.tie(NULL);

cout.tie(NULL);

int n, q, t;

cin>>t;

bin_log.push_back(-1); //bin_log[0]

bin_log.push_back(0); //bin_log[1]

while (t--)

{

cin>>n>>q;

lookup.clear();

nextEulerIndex = 0;

int nextLvl = 0;

vis[0] = 0;

for (int i = 1; vis[i] != 0; i++)

{

vis[i] = 0;

}

for (int i = 0; i < n-1; i++)

{

int a, b;

cin>>a>>b;

}

int index = 0;

eulerTree(1, index, nextLvl);

// nextEulerIndex = 0;

// printEulerTour(1, n, nextLvl);

makeBinaryLog(2*n);

RMQmin(2*n - 1);

while (q--)

{

int a, b;

cin>>a>>b;

int ans = 0;

for (int i = 0; i < n; i++)

{

int disA = shortestDistance( i, eulerTreeIndex[a]);

int disB = shortestDistance( i, eulerTreeIndex[b]);

ans += min(disA, disB);

}

cout<<ans<<"\n";

// printf("%d\n", ans);

}

}

return 0;

}``````