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
map<int, vector<int>> adj;
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)
{
adj[u].push_back(v);
adj[v].push_back(u);
}
// 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;
adj.clear();
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;
add_edge(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;
}