fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. #define crap ios::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
  4. typedef long long int ll;
  5. typedef unsigned long long ull;
  6. typedef std::vector<int> vi;
  7. typedef std::vector<ll> vll;
  8. typedef std::vector<vi > vvi;
  9. typedef std::vector<vll > vvll;
  10. typedef std::pair<int,int> ii;
  11. typedef std::pair< ll, ll > lp;
  12. typedef std::vector<ii> vii;
  13. typedef std::vector<vii > vvii;
  14.  
  15. #define pb push_back 
  16. #define PB pop_back
  17. #define pf push_front
  18. #define PF pop_front
  19. #define mp make_pair
  20. #define ub(a,b) upper_bound(all(a),b)
  21. #define lb(a,b) lower_bound(all(a),b)
  22. #define bs(a,b) binary_search(all(a),b)
  23. #define mem(a,b) memset(a,b,sizeof(a))
  24. #define in(a,n) f(i,0,n-1)cin>>a[i]
  25. #define in1(a,n) f(i,1,n)cin>>a[i]
  26. #define out(a,n) f(i,0,n-1)cout<<a[i]<<" ";cout<<"\n"
  27. #define ff first
  28. #define ss second
  29. #define f(i,a,b) for (int i=a;i<=b;i++)
  30. #define rf(i,a,b) for(int i=a;i>=b;i--)
  31. #define rep(i,n) f(i,0,n-1)
  32. #define clr(a) (a).clear()
  33. #define rz resize
  34. #define sqr(a) ((a) * (a))
  35. #define sz(a) int((a).size())
  36. #define all(a) (a).begin(), (a).end()
  37. #define rall(a) (a).rbegin() ,(a).rend()
  38. #define endl '\n'
  39.  
  40. const int N=(int)1e5 +5;
  41. const int LG=20;
  42.  
  43. int maxi[LG][N],P[LG][N],par[N],lvl[N];
  44.  
  45. vii gr[N];
  46.  
  47. void dfs(int u,int p=-1,int l=0)
  48. {
  49. 	par[u]=p;
  50. 	P[0][u]=p;
  51. 	lvl[u]=l;
  52. 	for (auto v:gr[u])
  53. 	{
  54. 		if (v.ff==p) continue;
  55. 		dfs(v.ff,u,l+1);
  56. 		maxi[0][v.ff]=v.ss;
  57. 	}
  58. }
  59.  
  60. int LCA(int u, int v)
  61. {
  62. 	int log;
  63. 	if (u==v)return u;
  64. 	if (lvl[u]<lvl[v])
  65. 		swap(u,v);
  66. 	for (log=1;1<<log <=lvl[u] ; log++);
  67. 	log--;
  68.  
  69. 	for (int i=log;i>=0;i--)
  70. 	{
  71. 		if (lvl[u]-(1<<i) >= lvl[v])
  72. 			u=P[i][u];
  73. 	}
  74.  
  75. 	if (u==v)
  76. 		return u;
  77. 	for (int i=log;i>=0;i--)
  78. 	{
  79. 		if (P[i][u]!=-1 && P[i][u]!=P[i][v])
  80. 			u=P[i][u],v=P[i][v];
  81. 	}
  82.  
  83. 	return P[0][u];
  84. }
  85.  
  86. int main(int argc, char const *argv[])
  87. {
  88. 	crap;
  89. 	int n;
  90. 	cin>>n;
  91. 	while (n)
  92. 	{
  93. 		rep(i,LG)
  94. 			rep(j,N)
  95. 				P[i][j]=-1,maxi[i][j]=INT_MIN,lvl[j]=0,par[j]=-1,gr[j].clear();
  96.  
  97. 		int u,v,c;
  98. 		rep(i,n-1)	
  99. 			cin>>u>>v>>c,gr[u].pb(mp(v,c)),gr[v].pb(mp(u,c));
  100. 		dfs(1);
  101. 		// cout<<"Yay!\n";
  102. 		//filling up the sparse table 
  103. 		f(i,1,LG-1)
  104. 		{
  105. 			f(j,1,n)
  106. 			{
  107. 				if (P[i-1][j]!=-1)
  108. 				{	
  109. 					P[i][j]=P[i-1][P[i-1][j]];
  110. 					maxi[i][j]=max(maxi[i-1][j],maxi[i-1][P[i-1][j]]);
  111. 				}
  112. 			}
  113. 		}
  114.  
  115. 		int q;
  116. 		cin>>q;
  117. 		while (q--)
  118. 		{
  119. 			cin>>u>>v;
  120. 			int lca=LCA(u,v);
  121. 			int mpath1=INT_MIN,mpath2=INT_MIN;
  122. 			for (int i=LG-1;i>=0;i--)
  123. 			{
  124. 				if (lvl[u]-(1<<i) >= lvl[lca])
  125. 				{
  126. 					mpath1=max(mpath1,maxi[i][u]);
  127. 					u=P[i][u];
  128. 				}
  129. 			}
  130. 			for (int i=LG-1;i>=0;i--)
  131. 			{
  132. 				if (lvl[v]-(1<<i) >= lvl[lca])
  133. 				{
  134. 					mpath2=max(mpath2,maxi[i][v]);
  135. 					v=P[i][v];
  136. 				}
  137. 			}
  138.  
  139. 			// if (mpath1==INT_MIN)
  140. 			// 	cout<<mpath2<<endl;
  141. 			// else if (mpath2==INT_MIN)
  142. 			// 	cout<<mpath1<<endl;
  143. 			// else
  144. 			cout<<max(mpath1,mpath2)<<endl;
  145. 		}
  146. 		cin>>n;
  147. 	}
  148.  
  149.  
  150.  
  151. 	return 0;
  152. }
Runtime error #stdin #stdout 0s 33984KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/bRUsj6
language:
C++14 (gcc 8.3)
created:
7 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!