#include <bits/stdc++.h>
using namespace std;

#define fo(i, n) for (int i = 0; i < n; i++)
#define count(n) for (int i = 1; i <= n; i++)
#define ll long long int
#define l long int
#define ld long double
#define ia(arr, n) fo(i, n) cin >> arr[i]
#define mo % 1000000007
#define precise(x) fixed << setprecision(x)

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int t;
    cin >> t;
    while (t--)
    {
        int n;
        string s;
        cin >> n >> s;
        int alice = 0, bob = 0;
        for (int i = 0; i < n; i++)
        {
            alice += s[i] == 'A';
            bob += s[i] == 'B';
            if (alice == 11)
            {
                 cout << "Alice" << '\n';
                 break;
            }
            if (bob == 11)
            {
                 cout << "Bob" << '\n';
                 break;
            }
         }

    }
    return 0;
}

#define ll long long int
#include<bits/stdc++.h>
#define loop(i,a,b) for(ll i=a;i<b;++i)
#define rloop(i,a,b) for(ll i=a;i>=b;i--)
#define in(a,n) for(ll i=0;i<n;++i) cin>>a[i];
#define pb push_back
#define mk make_pair
#define all(v) v.begin(),v.end()
#define dis(v) for(auto i:v)cout<<i<<" ";cout<<endl;
#define display(arr,n) for(int i=0; i<n; i++)cout<<arr[i]<<" ";cout<<endl;
#define fast ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);srand(time(NULL));
#define l(a) a.length()
#define fr first
#define sc second
#define mod 1000000007
#define endl '\n'
#define yes cout<<"Yes"<<endl;
#define no cout<<"No"<<endl;
using namespace std;
#define debug(x) cerr << #x<<" "; _print(x); cerr << endl;
void _print(ll t) {cerr << t;}
void _print(int t) {cerr << t;}
void _print(string t) {cerr << t;}
void _print(char t) {cerr << t;}
void _print(double t) {cerr << t;}
template <class T, class V> void _print(pair <T, V> p);
template <class T> void _print(vector <T> v);
template <class T> void _print(set <T> v);
template <class T, class V> void _print(map <T, V> v);
template <class T> void _print(multiset <T> v);
template <class T, class V> void _print(pair <T, V> p) {cerr << "{"; _print(p.fr); cerr << ","; _print(p.sc); cerr << "}";}
template <class T> void _print(vector <T> v) {cerr << "[ "; for (T i : v) {_print(i); cerr << " ";} cerr << "]";}
template <class T> void _print(set <T> v) {cerr << "[ "; for (T i : v) {_print(i); cerr << " ";} cerr << "]";}
template <class T> void _print(multiset <T> v) {cerr << "[ "; for (T i : v) {_print(i); cerr << " ";} cerr << "]";}
template <class T, class V> void _print(map <T, V> v) {cerr << "[ "; for (auto i : v) {_print(i); cerr << " ";} cerr << "]";}

ll add(ll x,ll y)  {ll ans = x+y; return (ans>=mod ? ans - mod : ans);}
ll sub(ll x,ll y)  {ll ans = x-y; return (ans<0 ? ans + mod : ans);}
ll mul(ll x,ll y)  {ll ans = x*y; return (ans>=mod ? ans % mod : ans);}


void solve(){
    int n;  cin>>n;
    assert(n>=1 && n<=21);
    string s;   cin>>s;
    assert(l(s) == n);
    int cnt = count(all(s),'A');
    assert(cnt >=11 || (n-cnt) >= 11);
    int cnt1=0,cnt2 = 0;
    loop(i,0,n){
        if(s[i] == 'A') cnt1++;
        else cnt2++;
        if(cnt1 == 11 || cnt2 == 11)    break;
    }
    assert(cnt1 == 11 || cnt2 == 11);
    if(cnt1 == 11)  cout<<"Alice\n";
    else cout<<"Bob\n";
}


int main()
{
    fast
    int t; cin>>t;
    while(t--) solve();
    return 0;
}

Suppose you have $$$2$$$ variables $$$a$$$ and $$$b$$$.$$$ (a ≤ b)$$$. which value you will decrease such that product will be minimum.

If you decrease greater value ($$$b$$$) than now you have $$$a*(b-1)$$$ and if you decrease $$$a$$$ than you have $$$b*(a-1)$$$. which value is smaller?

You will decrease smaller value first if possible...

Those who were getting TLE in this question, try to use Fast I/O.

#include <bits/stdc++.h>
using namespace std;

#define fo(i, n) for (ll i = 0; i < n; i++)
#define count(n) for (ll i = 1; i <= n; i++)
#define ll long long int
#define l long int
#define ld long double
#define ia(arr, n) fo(i, n) cin >> arr[i]
#define mo % 1000000007
#define precise(x) fixed << setprecision(x)

int p = 1e9 + 7;

ll add(ll a, ll b)
{
    return (((a % p) + (b % p)) % p);
}
ll sub(ll a, ll b)
{
    return (((a % p) - (b % p)) % p);
}
ll mul(ll a, ll b)
{
    return (((a % p) * (b % p)) % p);
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int t;
    cin >> t;
    while (t--)
    {
        ll n, m;
        cin >> n >> m;
        vector<ll> a(n);
        fo (i, n) { cin >> a[i]; }
        sort(a.begin(), a.end());
        ll ans = 1;
        fo (i, n)
        {
            if (m > 0 && a[i] > 1)
            {
                ll minus = min(m, a[i] - 1);
                a[i] = sub(a[i], minus);
                m = sub(m, minus);
            }
            ans = mul(ans, a[i]);
        }
        cout << ans << "\n";
    }
    return 0;
}

#define ll long long int
#include<bits/stdc++.h>
#define loop(i,a,b) for(ll i=a;i<b;++i)
#define rloop(i,a,b) for(ll i=a;i>=b;i--)
#define in(a,n) for(ll i=0;i<n;++i) cin>>a[i];
#define pb push_back
#define mk make_pair
#define all(v) v.begin(),v.end()
#define dis(v) for(auto i:v)cout<<i<<" ";cout<<endl;
#define display(arr,n) for(int i=0; i<n; i++)cout<<arr[i]<<" ";cout<<endl;
#define fast ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);srand(time(NULL));
#define l(a) a.length()
#define fr first
#define sc second
#define mod 1000000007
#define endl '\n'
#define yes cout<<"Yes"<<endl;
#define no cout<<"No"<<endl;
using namespace std;
#define debug(x) cerr << #x<<" "; _print(x); cerr << endl;
void _print(ll t) {cerr << t;}
void _print(int t) {cerr << t;}
void _print(string t) {cerr << t;}
void _print(char t) {cerr << t;}
void _print(double t) {cerr << t;}
template <class T, class V> void _print(pair <T, V> p);
template <class T> void _print(vector <T> v);
template <class T> void _print(set <T> v);
template <class T, class V> void _print(map <T, V> v);
template <class T> void _print(multiset <T> v);
template <class T, class V> void _print(pair <T, V> p) {cerr << "{"; _print(p.fr); cerr << ","; _print(p.sc); cerr << "}";}
template <class T> void _print(vector <T> v) {cerr << "[ "; for (T i : v) {_print(i); cerr << " ";} cerr << "]";}
template <class T> void _print(set <T> v) {cerr << "[ "; for (T i : v) {_print(i); cerr << " ";} cerr << "]";}
template <class T> void _print(multiset <T> v) {cerr << "[ "; for (T i : v) {_print(i); cerr << " ";} cerr << "]";}
template <class T, class V> void _print(map <T, V> v) {cerr << "[ "; for (auto i : v) {_print(i); cerr << " ";} cerr << "]";}

ll add(ll x,ll y)  {ll ans = x+y; return (ans>=mod ? ans - mod : ans);}
ll sub(ll x,ll y)  {ll ans = x-y; return (ans<0 ? ans + mod : ans);}
ll mul(ll x,ll y)  {ll ans = x*y; return (ans>=mod ? ans % mod : ans);}
ll N = 0;

void solve(){
    int n;   cin>>n;
    int m;  cin>>m;
    vector<int> v(n);   in(v,n);
    assert(n>=1 && n<=1e6);
    assert(m>=1 && m<=1e5);
    for(auto i:v)   assert(i>=1 && (i<=1e8));
    N+=n;
    sort(all(v));
    loop(i,0,n){
        if(v[i] == 1)   continue;        if(v[i]-1 <= m) m-=(v[i]-1),v[i] =1 ;
        else v[i]-=m,m=0;
    }
    ll ans = 1;
    loop(i,0,n) ans = mul(ans,v[i]);
    cout<<ans<<endl;
}


int main()
{
    fast
    int t; cin>>t;
    assert(t>=1 && t<=1e5);
    while(t--) solve();
    assert(N<=1e6);
    return 0;
}

Try to derive mathematical equation for $$$k$$$.

For $$$ y \mod x$$$ $$$!=$$$ $$$0$$$ value cannot be achievable, so the answer for this will be $$$-1$$$.

For $$$ y \mod x = 0 $$$,here in the above formula maximum value of $$$n$$$ will be always smaller than $$$64$$$(depending on value of $$$k$$$), except for $$$k = 1$$$. For $$$k = 1$$$ value can be achievable in $$$y/x$$$ steps. You can fix the value of $$$n$$$, now your left side is constant, and now you have to check left side number in base $$$k$$$. Number of on-bit in the left side number must be equal to $$$n$$$. Value of on-bit in the left side number must be less or equal to 1 and also left side number must be divisible by $$$k$$$. $$$(Why?)$$$

#include <bits/stdc++.h>
#include <iostream>
#define ull long long int
using namespace std;
#define maxlen 100000

bool sortVec(const vector<ull> &l, const vector<ull> &r){
	if (l[1]==r[1]){
		if (l[0]==r[0])return l[2] > r[2];
		else return l[0] > r[0];
	}
	else return l[1] > r[1];
}

ull check(ull n,ull k){
	ull c = 0;
	ull tmp=n;
	while(tmp>0){
		ull rmd=tmp%k;
		tmp=tmp/k;
		if(rmd>=2)
		return -1;
		
		if(rmd==1)
		c++;
	}
	return c;
}
ull val(ull n,ull k){
	ull c = 0;

	for (ull i = 0;n>0; i++){
		ull rmd=n%k;
		if(rmd==1)
		c+=i;

		n=n/k;
	}
	return c;
}
void solve(){
	ull x, y,k;
	cin>>x>>y>>k;
	if (y%x != 0 || x>y){
		cout<<"-1"<<"\n";
		return;
	}
	else{
	    if(x==y){
		    cout<<1<<endl;
		    return ;
		}
		y=y/x;
		if(k==1){
			cout<<y<<endl;
			return ;
		}
	
		for (ull i = 0; i < 64; i++){
			
			//cout<<check(y*(k-1)+i,k)<<" "<<i<<" "<<y+i<<"\n";
			if((y*(k-1)+i)%k)
			continue;

			if (check((y*(k-1)+i),k)==i){
				//(i-1) for breaks
				cout<<val((y*(k-1)+i),k)+i-1<<"\n";
				return;
			}
		}
		cout<<"-1"<<"\n";
	}
}

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

#define ll long long int
#include<bits/stdc++.h>
#define loop(i,a,b) for(ll i=a;i<b;++i)
#define rloop(i,a,b) for(ll i=a;i>=b;i--)
#define in(a,n) for(ll i=0;i<n;++i) cin>>a[i];
#define pb push_back
#define mk make_pair
#define all(v) v.begin(),v.end()
#define dis(v) for(auto i:v)cout<<i<<" ";cout<<endl;
#define display(arr,n) for(int i=0; i<n; i++)cout<<arr[i]<<" ";cout<<endl;
#define fast ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);srand(time(NULL));
#define l(a) a.length()
#define fr first
#define sc second
#define mod 1000000007
#define endl '\n'
#define yes cout<<"Yes"<<endl;
#define no cout<<"No"<<endl;
using namespace std;
#define debug(x) cerr << #x<<" "; _print(x); cerr << endl;
void _print(ll t) {cerr << t;}
void _print(int t) {cerr << t;}
void _print(string t) {cerr << t;}
void _print(char t) {cerr << t;}
void _print(double t) {cerr << t;}
template <class T, class V> void _print(pair <T, V> p);
template <class T> void _print(vector <T> v);
template <class T> void _print(set <T> v);
template <class T, class V> void _print(map <T, V> v);
template <class T> void _print(multiset <T> v);
template <class T, class V> void _print(pair <T, V> p) {cerr << "{"; _print(p.fr); cerr << ","; _print(p.sc); cerr << "}";}
template <class T> void _print(vector <T> v) {cerr << "[ "; for (T i : v) {_print(i); cerr << " ";} cerr << "]";}
template <class T> void _print(set <T> v) {cerr << "[ "; for (T i : v) {_print(i); cerr << " ";} cerr << "]";}
template <class T> void _print(multiset <T> v) {cerr << "[ "; for (T i : v) {_print(i); cerr << " ";} cerr << "]";}
template <class T, class V> void _print(map <T, V> v) {cerr << "[ "; for (auto i : v) {_print(i); cerr << " ";} cerr << "]";}

ll add(ll x,ll y)  {ll ans = x+y; return (ans>=mod ? ans - mod : ans);}
ll sub(ll x,ll y)  {ll ans = x-y; return (ans<0 ? ans + mod : ans);}
ll mul(ll x,ll y)  {ll ans = x*y; return (ans>=mod ? ans % mod : ans);}


pair<ll,ll> fn(ll n, ll x)
{
    ll vl1 = 0,vl2 = 0,cnt= 0;
	while (n > 0) {
		int rem = n % x;
		if (rem >= 2) return {-1,-1};
        if(rem) vl1++,vl2+=cnt;
        cnt++;
		n = n/x;
	}
	return {vl1,vl2};
}


void solve(){
    ll x,y,k; cin>>x>>y>>k;
    assert(x>=1 && x<=1e18 && y>=1 && y<=1e18 && k>=1 && k<=10);
    ll ans = INT_MAX;
    if(y%x) {cout<<-1<<endl;    return;}
    if(k == 1 || x == y){
        cout<<y/x<<endl;
        return;
    }
    ll tmp3 = y/x;
    ll mx_vl = log10(LONG_LONG_MAX)/log10(k);
    loop(i,1,mx_vl+1){
        ll tmp = tmp3,vl = 0,vl2=tmp3;
        pair<ll,ll> p = fn(((k-1)*(tmp3)+i),k);
        if(((k-1)*(tmp3)+i)%k)  continue;
        vl = p.fr,vl2 = p.sc;
        if(vl == i){
            ans = min(ans,vl2+i);
        }
    }
    if(ans == INT_MAX)  cout<<-1<<endl;
    else cout<<ans-1<<endl;
}


int main()
{
    fast
    int t; cin>>t;
    assert(t >=1 && t<=1e5);
    while(t--) solve();
    return 0;
}

Firstly we have to take mod of all the elements with $$$(A+B)$$$ because when any number is greater than $$$(A+B)$$$, there is a series of operations you and the bot can do. When it becomes less than $$$(A+B)$$$, it decides that either of you can do the operations on it or not, and if it's less than A+B then either only one of you can do operation or neither of you can perform operation on it.

After doing this, all the elements are now less than $$$(A+B)$$$. As the bot made the last move, so now it’s your chance. You check if any element is $$$>= A$$$, then you subtract it with $$$A$$$. If there is no such element, you lose, else the bot will check now if there is any element such that it is $$$>=B$$$. If there is no such element, it loses, and you win, else you lose because now there will be no element that can be $$$>= A$$$.

#include <bits/stdc++.h>
using namespace std;
int main(){

  int test;
  cin>>test;

  while(test--){
    int N, X, Y;
    cin >> N >> X >> Y;
    vector<int> A(N);
    for (int i = 0; i < N; i++){
      cin >> A[i];
    }
    for (int i = 0; i < N; i++){
      A[i] %= X + Y;
    }
    
    bool ok = 1;

    for(int i=0;i<N;i++){
      if(A[i]>=X){
        ok = false;
        A[i]-=X;
      }
    }

    if(ok){
      cout<<0<<'\n';
    }

    else{
      ok = 1;

      for(int i=0;i<N;i++){
        if(A[i]>=Y){
          ok = false;
          A[i]-=Y;
        }
      }

      if(ok)
      cout<<1<<'\n';
      else
      cout<<0<<'\n';
    }
  }
}

#include <bits/stdc++.h>
#include <iostream>
#define ull long long int
using namespace std;
bool sortVec(const vector<ull> &l, const vector<ull> &r){
	return l[0] < r[0];
}


void solve(){
	ull n, a, b;
	cin>>n>>a>>b;
	ull arr[n];
	ull ga = 0, gb = 0;
	for (ull i = 0; i < n; i++){
		cin>>arr[i];
		arr[i] = arr[i]%(a+b);
		if (arr[i] >= a)ga++;
		if (arr[i] >= b)gb++;
	}
	if (ga==0){
		cout<<0<<"\n";
	}
	else if (ga >= gb){
		cout<<1<<"\n";
	}
	else{
		cout<<0<<"\n";
	}
}

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

As given in the question distance between $$$2$$$ node is the weight of max edge between them. So a good idea to find these values for every node is to make a table(array) and store values in it.

We start by making $$$2$$$ arrays, one to store distance to all nodes below the current node(lets name it $$$D$$$) and one for all other node(lets name it $$$U$$$).

We perform a DFS and calculate $$$D$$$, when we reach a particular node we would have calculated $$$D$$$ for all its immediate children we traverse through them is a nodes distance from the child is less than the weight of edge from current node to the child we put note the distance of that node as weight of the edge(as it would be the max edge) else we keep it same(max edge is edge other than one connecting node and the child).

For the root $$$D$$$ and $$$U$$$ are the same.

Then we perform another DFS and repeat the process but this time for $$$U$$$ and considering edge from current node to the parent. Read the solution code understand more.

#include <bits/stdc++.h>
#include <iostream>
#define ull long long int
using namespace std;
#define maxlen 2*100000
#define edg_wt 100
bool sortVec(const vector<ull> &l, const vector<ull> &r){
	if (l[1]==r[1]){
		if (l[0]==r[0])return l[2] > r[2];
		else return l[0] > r[0];
	}
	else return l[1] > r[1];
}

vector<vector<ull>> adj(maxlen+1);
vector<vector<ull>> weight(maxlen+1);
vector<ull> parent(maxlen+1, 0);
vector<vector<ull>> up(maxlen+1, vector<ull> (edg_wt+1, 0));
vector<vector<ull>> down(maxlen+1, vector<ull> (edg_wt+1, 0));
vector<ull> val(maxlen+1);
ull temp[edg_wt+1]={0};

void get_parent(ull root, ull p){
	parent[root]=p;
	//cout<<root<<" ";
	for (ull i = 0; i < adj[root].size(); i++){
		if (adj[root][i]!=p){
			get_parent(adj[root][i], root);
		}
	}
}

void calc_down(ull root, ull p){
	for (ull i = 0; i < adj[root].size(); i++){
		if (adj[root][i]!=p){
			calc_down(adj[root][i], root);
		}
	}
	//cout<<root<<"\n";
	for (ull i = 0; i < adj[root].size(); i++){
		if (adj[root][i]!=p){
			//cout<<weight[root][i]<<" ";
			down[root][weight[root][i]]++;
			for (ull j = 0 ; j <= edg_wt; j++){
				if (j > weight[root][i])
				down[root][j]+=down[adj[root][i]][j];
				else
				down[root][weight[root][i]]+=down[adj[root][i]][j];
			}
		}
	}
	//cout<<"\n";
}
void calc_up(ull root, ull p, ull up_ed){
	for (ull i = 0; i <= edg_wt; i++){
		temp[i] = up[p][i];
	}
	for (ull i = 0; i <= edg_wt; i++){
		if (i < up_ed){
			temp[up_ed]-=down[root][i];
		}
		else{
			temp[i]-=down[root][i];
		}
	}
	for (ull i = 0; i < edg_wt+1; i++){
		if (i < up_ed)up[root][up_ed]+=temp[i];
		else up[root][i]+=temp[i];
		up[root][i]+=down[root][i];
	}
	for (ull i = 0; i < adj[root].size(); i++){
		if (adj[root][i]!=p){
			calc_up( adj[root][i], root, weight[root][i]);
		}
	}
}

/*
11 0
1 4 2
1 3 4
4 6 8
7 4 7
8 6 2
6 5 5
3 2 3
3 9 6
10 2 6
2 11 9
*/

void solve(){
	ull n, q;
	cin>>n>>q;
	ull u, v, w;
	for (ull i = 0; i < n-1; i++){
		cin>>u>>v>>w;
		adj[u].push_back(v);
		weight[u].push_back(w);
		
		adj[v].push_back(u);
		weight[v].push_back(w);
	}
	get_parent(1, 0);
	calc_down(1, 0);
	/*cout<<"\n";
	for (ull i = 1; i <= n; i++){
		cout<<i<<"->"<<" ";
		for (ull j = 1; j <= edg_wt; j++){
			cout<<down[i][j]<<" ";
		}
		cout<<"\n";
	}*/
	for (ull i = 0; i <= edg_wt; i++){
		up[1][i]=down[1][i];
	}
	for (ull i = 0; i < adj[1].size(); i++){
		if (adj[1][i]!=0){
			calc_up( adj[1][i], 1, weight[1][i]);
		}
	}
	/*cout<<"\n";
	for (ull i = 1; i <= n; i++){
		cout<<i<<"->"<<" ";
		for (ull j = 1; j <= edg_wt; j++){
			cout<<up[i][j]<<" ";
		}
		cout<<"\n";
	}
	cout<<"\n";*/
	for (ull i = 1; i <= n; i++){
		ull v = 0;
		for (ull j = 0; j <= edg_wt; j++){
			v += j*(up[i][j]);
		}
		val[i]=v;
		//cout<<v<<" ";
	}
	ull num;
	///cout<<"\n";
	for (ull i = 0; i < q; i++){
		cin>>num;
		cout<<val[num]<<"\n";
	}
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); 
	//int t;
	//cin>>t;
	//while(t--){
        
	//freopen ("input11.txt", "r", stdin);
		solve();
	//}
	return 0;
}

#define ll long long int
#include<bits/stdc++.h>
#define loop(i,a,b) for(ll i=a;i<b;++i)
#define rloop(i,a,b) for(ll i=a;i>=b;i--)
#define in(a,n) for(ll i=0;i<n;++i) cin>>a[i];
#define pb push_back
#define mk make_pair
#define all(v) v.begin(),v.end()
#define dis(v) for(auto i:v)cout<<i<<" ";cout<<endl;
#define display(arr,n) for(int i=0; i<n; i++)cout<<arr[i]<<" ";cout<<endl;
#define fast ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);srand(time(NULL));
#define l(a) a.length()
#define fr first
#define sc second
#define mod 1000000007
#define endl '\n'
#define yes cout<<"Yes"<<endl;
#define no cout<<"No"<<endl;
using namespace std;
#define debug(x) cerr << #x<<" "; _print(x); cerr << endl;
void _print(ll t) {cerr << t;}
void _print(int t) {cerr << t;}
void _print(string t) {cerr << t;}
void _print(char t) {cerr << t;}
void _print(double t) {cerr << t;}
template <class T, class V> void _print(pair <T, V> p);
template <class T> void _print(vector <T> v);
template <class T> void _print(set <T> v);
template <class T, class V> void _print(map <T, V> v);
template <class T> void _print(multiset <T> v);
template <class T, class V> void _print(pair <T, V> p) {cerr << "{"; _print(p.fr); cerr << ","; _print(p.sc); cerr << "}";}
template <class T> void _print(vector <T> v) {cerr << "[ "; for (T i : v) {_print(i); cerr << " ";} cerr << "]";}
template <class T> void _print(set <T> v) {cerr << "[ "; for (T i : v) {_print(i); cerr << " ";} cerr << "]";}
template <class T> void _print(multiset <T> v) {cerr << "[ "; for (T i : v) {_print(i); cerr << " ";} cerr << "]";}
template <class T, class V> void _print(map <T, V> v) {cerr << "[ "; for (auto i : v) {_print(i); cerr << " ";} cerr << "]";}

ll add(ll x,ll y)  {ll ans = x+y; return (ans>=mod ? ans - mod : ans);}
ll sub(ll x,ll y)  {ll ans = x-y; return (ans<0 ? ans + mod : ans);}
ll mul(ll x,ll y)  {ll ans = x*y; return (ans>=mod ? ans % mod : ans);}
map<pair<int,int>,int> m;
vector<vector<int>> v;
vector<int> vis;
vector<vector<int>> freq;
vector<int> final;


vector<int> fn(int i,int par){
    vector<int> ans(101,0);
    for(auto j:v[i]){
        if(j == par)    continue;
        vector<int> tmp = fn(j,i);
        int vl = m[{i,j}];
        for(int k=vl;k<=100;k++)    ans[k]+=tmp[k];
        ans[vl]++;
        for(int k=0;k<vl;k++)   ans[vl]+=tmp[k];
    }
    return freq[i] = ans;
}



void fn2(int i,int par,vector<int> vec){
    vector<int> ans(101,0);
    if(par!=-1){
        ans = freq[par];
        int vl = m[{i,par}];
        for(int j=0;j<=100;j++) if(j<=vl)     ans[vl]+=vec[j];  else ans[j]+=vec[j];
        for(int j=0;j<=100;j++){
            if(j<=vl)   ans[vl]-=freq[i][j];
            else ans[j]-=freq[i][j];
        }
        int vl2 = 0;
        for(int j=0;j<=100;j++) if(j<vl)   ans[vl]+=ans[j],ans[j]=0;
        for(int j=0;j<=100;j++) if(j<=vl) vl2+=(vl*ans[j]); else vl2+=(j*ans[j]);
        for(int j=0;j<=100;j++) vl2+=(j*freq[i][j]);
        final[i] = vl2;
    }
    for(auto j:v[i]){
        if(j == par)    continue;
        fn2(j,i,ans);
    }
}




void solve(){
    ll n,q; cin>>n>>q;
    assert(n>=1 && n<=2e5 && q>=1 && q<=2e5);
    v.assign(n+1,{});
    freq.assign(n+1,{});
    vis.assign(n+1,0);
    final.assign(n+1,0);
    loop(i,1,n){
        ll a,b,w;   cin>>a>>b>>w;
        assert(a>=1 && a<=n && b>=1 &&  b<=n && w>=1 && w<=100);
        v[a].pb(b);
        v[b].pb(a);
        m[{a,b}] = m[{b,a}]  = w;
    }
    fn(1,-1);
    vector<int> tmp(101,0);
    fn2(1,-1,tmp);
    int vl = 0;
    for(int j=0;j<=100;j++) vl+=(j*freq[1][j]);
    final[1] = vl;
    while(q--){
        int k;  cin>>k;
        cout<<final[k]<<endl;
    }
}


int main()
{
    fast
    int t = 1;
    while(t--) solve();
    return 0;
}

For gcd you just have to calculate for prime-factors only. there will be at most $$$6$$$ prime-factor for any number in $$$[1,100000]$$$.

Suppose you have store all the possible value of $$$(v[i]/x)$$$ ($$$x$$$ is prime number) in the binary form, for all $$$i$$$ in the Trie with indexes. Now if you fixed one prime number than for minimum value you will try to search for all bits $$$0$$$ and for maximum value you will try to search for all bits $$$1$$$. From this you can handle type of query $$$1$$$.

Assume that you don't have to delete the element in the array but you just have to erase the value of that index from Trie. For each query calculate the original value of $$$l$$$ and $$$r$$$ in the original array from the help of Fenwick tree/Segment tree.

#define ll long long int
#include<bits/stdc++.h>
#define loop(i,a,b) for(ll i=a;i<b;++i)
#define rloop(i,a,b) for(ll i=a;i>=b;i--)
#define in(a,n) for(ll i=0;i<n;++i) cin>>a[i];
#define pb push_back
#define mk make_pair
#define all(v) v.begin(),v.end()
#define dis(v) for(auto i:v)cout<<i<<" ";cout<<endl;
#define display(arr,n) for(int i=0; i<n; i++)cout<<arr[i]<<" ";cout<<endl;
#define fast ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);srand(time(NULL));
#define l(a) a.length()
#define fr first
#define sc second
#define mod 1000000007
#define endl '\n'
#define yes cout<<"Yes"<<endl;
#define no cout<<"No"<<endl;
using namespace std;
#define debug(x) cerr << #x<<" "; _print(x); cerr << endl;
void _print(ll t) {cerr << t;}
void _print(int t) {cerr << t;}
void _print(string t) {cerr << t;}
void _print(char t) {cerr << t;}
void _print(double t) {cerr << t;}
template <class T, class V> void _print(pair <T, V> p);
template <class T> void _print(vector <T> v);
template <class T> void _print(set <T> v);
template <class T, class V> void _print(map <T, V> v);
template <class T> void _print(multiset <T> v);
template <class T, class V> void _print(pair <T, V> p) {cerr << "{"; _print(p.fr); cerr << ","; _print(p.sc); cerr << "}";}
template <class T> void _print(vector <T> v) {cerr << "[ "; for (T i : v) {_print(i); cerr << " ";} cerr << "]";}
template <class T> void _print(set <T> v) {cerr << "[ "; for (T i : v) {_print(i); cerr << " ";} cerr << "]";}
template <class T> void _print(multiset <T> v) {cerr << "[ "; for (T i : v) {_print(i); cerr << " ";} cerr << "]";}
template <class T, class V> void _print(map <T, V> v) {cerr << "[ "; for (auto i : v) {_print(i); cerr << " ";} cerr << "]";}

ll add(ll x,ll y)  {ll ans = x+y; return (ans>=mod ? ans - mod : ans);}
ll sub(ll x,ll y)  {ll ans = x-y; return (ans<0 ? ans + mod : ans);}
ll mul(ll x,ll y)  {ll ans = x*y; return (ans>=mod ? ans % mod : ans);}


class Node{
    public: 
    Node* link[2];
   set<int> s;
    Node(){
        link[0] = link[1] = NULL;
    }
};

// Implementation of Trie
class Trie{
    public:
    Node* root = new Node();
    // inserting value and index.
    void insert(int n,int idx){
        Node* ne = root;
        for(int i=17;i>=0;i--){
            int bit = (n>>i)&1;
            if(ne->link[bit] == NULL)  {
                ne->link[bit] = new Node();
            }
            ne = ne->link[bit];
            ne->s.insert(idx);
        }
    }

    // finding maximum and minimum value and index in [l,r].
    pair<int,int> find(int x,int l,int r){
        Node *ne = root;
        int i = 17,ans = 0,idx=-1;
        while(ne && i>=0){
            int bit = (x>>i)&1;
            if(ne->link[bit]){
                auto it = ne->link[bit]->s.lower_bound(l);
                if(it!=ne->link[bit]->s.end() && *it <= r) {
                    ne = ne->link[bit];
                    if(bit == 1)    ans+=(1ll<<i);
                }
                else if(bit)    ne = ne->link[0];
                else ne = ne->link[1],ans+=(1ll<<i);
            }
            else if(bit)    ne = ne->link[0];
            else ne = ne->link[1],ans+=(1ll<<i);
            if(!ne)    return {-1,-1};
            i--;
        }
        if(i!=-1)   return {-1,-1};
        auto it = ne->s.lower_bound(l);
        if(it == ne->s.end() || *it>r)  return {-1,-1};
        idx = *it;
        return {ans,idx};
    }

    // removing perticular index from the trie.
    void erase(int idx,int old){
        Node *ne = root;
        for(int i=17;i>=0;i--){
            int bit = (old>>i)&1;
            ne = ne->link[bit];
            ne->s.erase(idx);
        }
    }
};



vector<int> spf(100000+1,INT_MAX),vec(20000+1,0);

// finding all prime factor of n
vector<int> prime_fact(int n){
    vector<int> ans = {1};
    while(n!=1){
        int x = spf[n];
        ans.push_back(x);
        while(n!=1 && spf[n] == x) n/=spf[n];
    }
    return ans;
}



// fenwick tree
int query(int i){
    if(i <= 0)   return 0;
    int ans = 0;
    for(;i;i-=(i&(-i))) ans+=vec[i];
    return ans;
}

void add_(int i,int vl){
    for(;i<=20000;i+=(i&(-i)))  vec[i]+=vl;
}


// for 2nd type of query-finding original position of x in the array.
int find_idx(int x){
    int l = 1,r = 2e4,idx;
    while(l<=r){
        int mid = (l+r)/2;
        int vl = query(mid);
        if(vl < x) l = mid+1;
        else r = mid-1,idx = mid;
    }
    return idx;
}


void solve(){
    vector<Trie> trie(100000+1);
    // input
    int n;  cin>>n;
    assert(n>=1 && n<=2e4);
    vector<int> v(n);   in(v,n);
    loop(i,0,n) assert(v[i]>=1 && v[i]<=1e5);
    // building trie
    loop(i,0,n){
        vector<int> factors = prime_fact(v[i]);
        for(auto j:factors) trie[j].insert(v[i]/j,i+1);
    }
    // 
    vector<int> final_ans;
    loop(i,1,2e4+1) add_(i,1);
    int q;  cin>>q;
    assert(q>=1 && q<=1e5);
    int j = 0;
    while(q--){
        // input
        int type ;  cin>>type;
        assert(type == 1 || type == 2);
        int l,r,x;  cin>>l>>r>>x;
        assert(l>=1 && r>=1 && r>=l);
        assert(x>=2 && x<=1e5);
        assert(r<=n-j);
        //
        l = find_idx(l);    // finding current position of l in original array
        r = find_idx(r);    // finding current position of r in original array
        //
        vector<int> factor = prime_fact(x);
        // 
        vector<pair<int,int>> ans1,ans2;     // ans1 for minimum value and ans2 for maximum value
        for(auto j:factor){
            if(j == 1)  continue;

            pair<int,int> p = trie[j].find(0,l,r);  // (000....0000) for minimum value 
            if(p.sc == -1 || p.sc>r || p.sc < l)    continue;
            ans1.push_back({p.fr*j,p.sc});
            p = trie[j].find((1ll<<18)-1,l,r);      // (1111...1111)  for maximum value
            ans2.pb({p.fr*j,p.sc});
        }
        // sorting all possible values
        sort(all(ans1));
        sort(all(ans2));
        // 
        if(type == 1){

            if(ans2.size() == 0)    final_ans.pb(-1);   // if no element is present with those conditions
            else final_ans.pb(ans2.back().fr-ans1[0].fr);   // otherwise ans will be maximum value - minimum value

        }
        else{

            if(!ans1.size()){
                pair<int,int> p = trie[1].find(0,l,r);  // if no element is present than finding minimum value
                ans1.push_back(p);
            }

            factor = prime_fact(ans1[0].fr);    // taking minimum value and removing that index it from the trie
            for(auto j:factor)  trie[j].erase(ans1[0].sc,ans1[0].fr/j);
            add_(ans1[0].sc,-1);
            final_ans.push_back(ans1[0].sc);
            j++;
        }
    }
    for(auto i:final_ans)   cout<<i<<endl;
}



int main()
{
    fast
    // finding smallest_prime_factor of all element in [1,100000].
    for(int i=2;i<=1e5;i++) spf[i] = i;
    for(int i=2;i<=1e5;i++){
        if(spf[i] == i){
            for(int j=i;j<=1e5;j+=i)    spf[j] = min(spf[j],i);
        }
    }
    int t = 1;
    while(t--) solve();
    return 0;
}