fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4. typedef vector<int> vi;
  5. typedef pair<int, int> ii;
  6. typedef long long ll;
  7. typedef pair<long long, long long> l4;
  8. typedef vector<long long> vll;
  9. typedef double db;
  10. typedef vector<double> vdb;
  11. typedef pair<double, double> dd;
  12. typedef set<int> si;
  13. typedef set<long long> sll;
  14. #define fi first
  15. #define se second
  16. #define matrix(a) vector< vector<a> >
  17. #define sz(a) int((a).size()) 
  18. #define lop(i,a,b) for (int i=a; i<=b; i++)
  19. #define vlop(i,v) lop(i,0,sz(v)-1)
  20. #define vlop1(i,v) lop(i,1,sz(v)-1)
  21. #define rlop(i,a,b) for (int i=b; i>=a; i--)
  22. #define vrlop(i,v) rlop(i,0,sz(v)-1)
  23. #define vrlop1(i,v) rlop(i,1,sz(v)-1)
  24. #define printv(i,v) vlop(i,v)cout<<v[i]<<" "
  25. #define printv1(i,v) vlop1(i,v)cout<<v[i]<<" "
  26. #define all(s) (s).begin(),(s).end()
  27. #define pb push_back
  28. #define enter cout<<'\n'
  29. #define lb(i,v) int(lower_bound(all(v),i)-v.begin())
  30. #define ub(i,v) int(upper_bound(all(v),i)-v.begin())
  31. void initialize(int start, vi& stree, vi& level, int l, int u) {
  32. 	if (sz(stree) - 1 < start)stree.resize(start + 1);
  33. 	if (l == u)stree[start] = l;
  34. 	else {
  35. 		initialize(2 * start, stree, level, l, (u + l) / 2);
  36. 		initialize(2 * start + 1, stree, level, (u + l) / 2 + 1, u);
  37. 		if (level[stree[start * 2]] < level[stree[start * 2 + 1]])stree[start] = stree[start * 2];
  38. 		else stree[start] = stree[start * 2 + 1];
  39. 	}
  40. 	return;
  41. }
  42.  
  43. int rmq(int start, vi& stree, vi& level, int i, int j, int l, int u) {
  44. 	if (j<l || i>u)return -1;
  45. 	if (l >= i&&u <= j)return stree[start];
  46. 	int t1 = rmq(2 * start, stree, level, i, j, l, (u + l) / 2);
  47. 	int t2 = rmq(2 * start + 1, stree, level, i, j, (u + l) / 2 + 1, u);
  48. 	if (t1 == -1)return t2;
  49. 	if (t2 == -1)return t1;
  50. 	if (level[t1] < level[t2])return t1;
  51. 	return t2;
  52. }
  53. void dfs(matrix(int)& alist, vi& tour, int root, vi& entry, vi& level, vi& visited,int currentlevel) {
  54. 	visited[root] = 1;
  55. 	tour.pb(root);
  56. 	level.pb(currentlevel);
  57. 	entry[root] = sz(tour) - 1;
  58. 	vlop(i, alist[root]) {
  59. 		if (!visited[alist[root][i]]) {
  60. 			dfs(alist, tour, alist[root][i], entry,level, visited,currentlevel+1);
  61. 			tour.pb(root);
  62. 			level.pb(currentlevel);
  63. 		}
  64. 	}
  65. 	return;
  66. }
  67.  
  68. int main(){
  69.     ios::sync_with_stdio(false);
  70.     int n,q;
  71.     cin>>n>>q;
  72.     matrix(int) alist(n+1);
  73.     int p;
  74.     lop(i,2,n){
  75.         cin>>p;
  76.         alist[i].pb(p);
  77.         alist[p].pb(i);
  78.     }
  79.     vi tour,level,entry(n + 1),visited(n + 1, 0),stree;
  80. 	dfs(alist, tour, 1, entry, level, visited,0);
  81. 	initialize(1, stree, level, 0, sz(level)-1);
  82. 	int a,b,c,ab,ac,bc,lab,lac,lbc,la,lb,lc;
  83. 	lop(query,1,q){
  84. 	    cin>>a>>b>>c;
  85. 	    ab=tour[rmq(1, stree, level, min(entry[a],entry[b]), max(entry[a],entry[b]), 0, sz(level) - 1)];
  86. 	    ac=tour[rmq(1, stree, level, min(entry[a],entry[c]), max(entry[a],entry[c]), 0, sz(level) - 1)];
  87. 	    bc=tour[rmq(1, stree, level, min(entry[c],entry[b]), max(entry[c],entry[b]), 0, sz(level) - 1)];
  88. 	    lab=level[entry[a]]+level[entry[b]]-level[entry[ab]]*2;
  89. 	    lac=level[entry[a]]+level[entry[c]]-level[entry[ac]]*2;
  90. 	    lbc=level[entry[b]]+level[entry[c]]-level[entry[bc]]*2;
  91. 	    la=(lab+lac-lbc)/2;
  92. 	    lb=(lab+lbc-lac)/2;
  93. 	    lc=(lbc+lac-lab)/2;
  94. 	    cout<<max(la,max(lb,lc))+1<<'\n';
  95. 	}
  96.     return 0;
  97. }
Success #stdin #stdout 0s 16056KB
comments (?)
stdin
copy 
4 1
1 2 3
1 2 3
stdout
copy 
2
https://ideone.com/Frk5fc
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!