#include <bits/stdc++.h>
using namespace std;
#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
#define lld long long int
//-4%3=-1
vector <int> edge[1000001],res;
int vis[1000001]={-1};
int n,arr[1000001];
void dfs(int x,int y,vector <int> v)
{
v.push_back(x);
if(x==y)
{
for(int i=0;i<v.size();i++)
{
res.push_back(arr[v[i]]);
}
return;
}
vis[x]=1;
int flag = 0;
if(!edge[x].empty())
{
for(int j=0;j<edge[x].size();j++)
{
if (vis[edge[x][j]]==-1)
{
dfs(edge[x][j],y,v);
flag = 1;
}
}
}
if (flag == 0)
{
v.pop_back();
}
}
int main() {
// your code goes here
ios_base::sync_with_stdio(false);
cin.tie(NULL);
lld t;
cin>>t;
while(t--)
{
int q,a,b;
cin>>n>>q;
for(int i=1;i<=n;i++)
cin>>arr[i];
for(int i=0;i<n-1;i++)
{
cin>>a>>b;
edge[a].push_back(b);
edge[b].push_back(a);
}
while(q--)
{
cin>>a>>b;
//memset(vis,-1,sizeof(vis));
for(int i=0;i<=1001;i++)
vis[i]=-1;
vector <int> v;
res.clear();
dfs(a,b,v);
/*cout<<"\n";
for(int i=0;i<res.size();i++)
cout<<res[i]<<" ";*/
sort(res.begin(),res.end());
int r=INT_MAX;
for(int i=0;i<res.size()-1;i++)
r=min(r,abs(res[i]-res[i+1]));
cout<<r<<"\n";
}
}
}
Why is this giving TLE for subtask 1? I have used dfs per query.
@galencolin @ssjgz @everule1