In this problem you have to find the maximum weight between a path.
Suppose in the sample test case 2 to 6 have a path 2->1->6
In here 2->1 the weight is 1 & 1->6 the weight is 2 so the maximum weight is MAX(1,2)=2
Again 5 to 2 there have a path 5->3->1->2
In here 5->3 the weight is 8 & 3->1 the weight is 5 & 1->2 the weight is 1 so the maximum weight is MAX(8,5,1)=8
Input:
6
1 2 1
1 3 5
3 4 3
3 5 8
1 6 2
3
2 6
5 2
4 6
0
Output:
2
8
5
Problem Link:
https://www.spoj.com/problems/NTICKETS/
Code:
///...................SUBHASHIS MOLLICK...................///
///.....DEPARTMENT OF COMPUTER SCIENCE AND ENGINEERING....///
///.............ISLAMIC UNIVERSITY,BANGLADESH.............///
///....................SESSION-(14-15)....................///
#include<bits/stdc++.h>
using namespace std;
#define sf(a) scanf("%d",&a)
#define sf2(a,b) scanf("%d %d",&a,&b)
#define sf3(a,b,c) scanf("%d %d %d",&a,&b,&c)
#define pf(a) printf("%d",a)
#define pf2(a,b) printf("%d %d",a,b)
#define pf3(a,b,c) printf("%d %d %d",a,b,c)
#define sfl(a) scanf("%lld",&a)
#define sfl2(a,b) scanf("%lld %lld",&a,&b)
#define sfl3(a,b,c) scanf("%lld %lld %lld",&a,&b,&c)
#define pfl(a) printf("%lld",a)
#define pfl2(a,b) printf("%lld %lld",a,b)
#define pfl3(a,b,c) printf("%lld %lld %lld",a,b,c)
#define nl printf("\n")
#define timesave ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define ll long long
#define pb push_back
#define MPI map<int,int>mp;
#define fr(i,n) for(i=0;i<n;i++)
#define fr1(i,n) for(i=1;i<=n;i++)
#define frl(i,a,b) for(i=a;i<=b;i++)
#define tz 100000
#define clr0(a) memset(a,0,sizeof(a))
#define clr1(a) memset(a,-1,sizeof(a))
/*primes in range 1 - n
1 - 100(1e2) -> 25 pimes
1 - 1000(1e3) -> 168 primes
1 - 10000(1e4) -> 1229 primes
1 - 100000(1e5) -> 9592 primes
1 - 1000000(1e6) -> 78498 primes
1 - 10000000(1e7) -> 664579 primes
large primes ->
104729 1299709 15485863 179424673 2147483647 32416190071 112272535095293 48112959837082048697
*/
//freopen("Input.txt","r",stdin);
//freopen("Output.txt","w",stdout);
//const int fx[]={+1,-1,+0,+0};
//const int fy[]={+0,+0,+1,-1};
//const int fx[]={+0,+0,+1,-1,-1,+1,-1,+1}; // Kings Move
//const int fy[]={-1,+1,+0,+0,+1,+1,-1,-1}; // Kings Move
//const int fx[]={-2, -2, -1, -1, 1, 1, 2, 2}; // Knights Move
//const int fy[]={-1, 1, -2, 2, -2, 2, -1, 1}; // Knights Move
#define N 100000
ll weight[20][N+5];
vector<pair<int,int> >vec[N+5];
int par[N+5],dis[N+5],vis[N+5],sparse[20][N+5];
void bfs(int src)
{
dis[src]=0;
par[src]=-1;
queue<int>q;
q.push(src);
while(!q.empty())
{
int u=q.front();
q.pop();
vis[u]=1;
for(int i=0;i<vec[u].size();i++)
{
int v=vec[u][i].first,w=vec[u][i].second;
if(vis[v]==0)
{
q.push(v);
dis[v]=dis[u]+1;
par[v]=u;
weight[0][v]=w;
}
}
}
}
void init()
{
for(int i=1;i<=N;i++)
{
sparse[0][i]=par[ i ];
for( int j = 1; 1 << j <= N; j++ )
{
sparse[j][i]=-1;
}
}
for(int j=1;1<<j<=N;j++ )
{
for(int i=1;i<=N;i++)
{
sparse[j][i]=sparse[j-1][sparse[j-1][i]];
weight[j][i]=max(weight[j-1][i],weight[j-1][sparse[j-1][i]]);
}
}
}
int lca( int u, int v )
{
int lg=0;
if(dis[u]<dis[v])
{
swap(u,v);
}
if(!dis[u])
{
return u;
}
for(lg=0;1<<lg<=dis[u];lg++);
lg--;
for(int i=lg;i>=0;i--)
{
if(dis[u]-(1<<i)>=dis[ v ] )
{
u=sparse[i][u];
}
}
if(u==v)
{
return u;
}
for(int i=lg;i>=0;i--)
{
if(sparse[i][u]!=-1&&sparse[i][u]!=sparse[i][v])
{
u=sparse[i][u];
v= sparse[i][v];
}
}
return par[u];
}
long long query( int u, int v )
{
int LCA=lca(u,v);
int uv,uu;
long long maxi=0;
for(uv=0;1<<uv<=dis[v];uv++);
uv--;
for(uu=0;1<<uu<=dis[u];uu++);
uu--;
if(!dis[u]&&!dis[v])
{
return maxi;
}
for(int i=uu;i>=0;i--)
{
if(dis[u]-(1<<i)>=dis[LCA])
{
maxi=max(maxi,weight[i][u]);
u=sparse[i][u];
}
}
for(int i=uv;i>=0;i--)
{
if(dis[v]-(1<<i)>=dis[ LCA ] )
{
maxi = max( maxi,weight[i][v]);
v=sparse[i][v];
}
}
return maxi;
}
main()
{
int n;
while(scanf("%d",&n)!=EOF)
{
if(n==0)
break;
for(int i=0;i<=N;i++)
{
vec[i].clear();
par[i]=-1;
dis[i]=0;
vis[i]=0;
for(int j=0;j<20;j++)
{
weight[j][i]=0;
//sparse[j][i]=-1;
}
}
int u,v,w;
for(int i=1;i<n;i++)
{
sf3(u,v,w);
vec[u].push_back({v,w});
vec[v].push_back({u,w});
}
bfs(1);
init();
int q;
sf(q);
for(int i=1;i<=q;i++)
{
sf2(u,v);
printf("%lld\n",query(u,v));
}
}
}
