fork download
copy 
  1. #include <bits/stdc++.h>
  2. #include <ext/pb_ds/assoc_container.hpp>
  3. using namespace std;
  4. using namespace __gnu_pbds;
  5.  
  6. #define fi first
  7. #define se second
  8. #define pb push_back
  9. //#define int long long
  10. #define sz(a) (int)a.size()
  11. #define all(a) begin(a),end(a)
  12. #define uid(a, b) uniform_int_distribution<int>(a, b)(rng)
  13.  
  14. mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
  15.  
  16. using ll = long long;
  17. using vi = vector<int>;
  18. using ar2 = array<int,2>;
  19. using ar3 = array<int,3>;
  20.  
  21. const int mxN = (int)2e5+2;
  22. const int INF = (int)2e9;
  23. const ll LINF = (ll)2e18;
  24. const int MOD = (int)1e9+7;
  25. const int mxLg = 20;
  26.  
  27. int n, dfs_timer;
  28. int st[mxN], en[mxN];
  29. vector<ar2> adj[mxN];
  30. int jmp[mxLg][mxN], mx[mxLg][mxN], mx2[mxLg][mxN];
  31.  
  32. bool isAnc(int a, int b){
  33. 	return st[a]<=st[b] and en[a]>=en[b];
  34. }
  35.  
  36. int lca(int a, int b){
  37. 	if(isAnc(a,b)) return a;
  38. 	if(isAnc(b,a)) return b;
  39. 	for(int i = mxLg-1; i>=0; i--)
  40. 		if(jmp[i][a] and !isAnc(jmp[i][a],b))
  41. 			a = jmp[i][a];
  42. 	return jmp[0][a];
  43. }
  44.  
  45. int max1(int a, int b){
  46. 	int ans = -1;
  47. 	for(int i = mxLg-1; i>=0; i--)
  48. 		if(jmp[i][a] and st[jmp[i][a]]>=st[b])
  49. 			ans=max(ans, mx[i][a]), a = jmp[i][a];
  50. 	return ans;
  51. }
  52.  
  53. int max2(int a, int b){
  54. 	multiset<int> S; S.clear();
  55. 	for(int i = mxLg-1; i>=0; i--){
  56. 		if(jmp[i][a] and st[jmp[i][a]]>=st[b]){
  57. 			S.insert(mx[i][a]); S.insert(mx2[i][a]);
  58. 			while(sz(S)>2) S.erase(begin(S));
  59. 			a = jmp[i][a];
  60. 		}
  61. 	}
  62. 	if(sz(S)>=2) return *prev(prev(end(S)));
  63. 	return -1;
  64. }
  65.  
  66. void dfs(int s, int p){
  67. 	st[s] = ++dfs_timer;
  68. 	for(auto [u,w] : adj[s]){
  69. 		if(u==p) continue;
  70. 		jmp[0][u] = s; mx[0][u] = w;
  71. 		dfs(u,s);
  72. 	}
  73. 	en[s] = dfs_timer;
  74. }
  75.  
  76. void solve(){
  77. 	cin >> n; 
  78. 	memset(mx,-1,sizeof(mx));
  79. 	memset(mx2,-1,sizeof(mx2));
  80. 	for(int i = 1; i < n; i++){
  81. 		int a, b, c; cin >> a >> b >> c;
  82. 		adj[a].pb({b,c}), adj[b].pb({a,c});
  83. 	}
  84. 	dfs(1,0);
  85. 	for(int j = 1; j < mxLg; j++){
  86. 		for(int i = 1; i <= n; i++){
  87. 			int k = jmp[j-1][i]; if(!k) continue;
  88. 			jmp[j][i] = jmp[j-1][k];
  89. 			mx[j][i] = max(mx[j-1][i], mx[j-1][k]);
  90. 			mx2[j][i] = min(mx[j-1][i], mx[j-1][k]);
  91. 			mx2[j][i] = max({mx2[j][i], mx2[j-1][i], mx2[j-1][k]});
  92. 		}
  93. 	}
  94. 	int q; cin >> q;
  95. 	while(q--){
  96. 		int a, b; cin >> a >> b;
  97. 		int c = lca(a,b);
  98. 		if(st[a]>st[b]) swap(a,b);
  99. 		if(c==a) cout << max2(b,a) << "\n";
  100. 		else cout << max({min(max1(a,c),max1(b,c)), max2(a,c), max2(b,c)}) << "\n";
  101. 	}
  102. }
  103.  
  104. int32_t main(){
  105.     ios_base::sync_with_stdio(false); cin.tie(0);
  106.     int t = 1; //cin >> t;
  107.     while(t--) solve();
  108. }
Success #stdin #stdout 0.01s 42916KB
comments (?)
stdin
copy 
4
1 2 2
2 3 3
3 4 4
2
1 3
2 4
stdout
copy 
2
3
https://ideone.com/ADH3Vr
language:
C++14 (gcc 8.3)
created:
1 day 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!