fork(2) download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. #define pb push_back
  4. #define f(i,n) for (int i = 0; i < n; i++)
  5. #define f1(i,n) for (int i = 1; i <= n; i++)
  6. #define s(x)	scanf("%d",&x)
  7. #define p(x)	printf("%d",x)
  8. #define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  9. #define N 100001
  10. #define lg 20
  11.  
  12. int lca[N][lg];
  13. vector<int> adj[N];
  14.  
  15. void dfs(int node)
  16. {
  17. 	f1(i,lg)
  18. 	{
  19. 		if(lca[node][i-1]==-1)
  20. 			lca[node][i]=-1;
  21. 		else
  22. 			lca[node][i]=lca[lca[node][i-1]][i-1];
  23. 	}
  24. 	f(i,adj[node].size())
  25. 	{
  26. 		//childCall
  27. 		int j=adj[node][i];
  28. 		//setChildParent
  29. 		lca[j][0]=node;
  30. 		//recursion
  31. 		dfs(j);
  32. 	}
  33. }
  34.  
  35. void delNode(int x)
  36. {
  37. 	f(i,lg)
  38. 		lca[x][i]=-1;
  39. }
  40.  
  41. void addNode(int x,int y)
  42. {
  43. 	lca[y][0]=x;
  44. 	f1(i,lg)
  45. 	{
  46. 		if(lca[y][i-1]==-1)
  47. 			lca[y][i]=-1;
  48. 		else
  49. 			lca[y][i]=lca[lca[y][i-1]][i-1];
  50. 	}
  51. }
  52.  
  53. int getKthNode(int x,int k)
  54. {
  55. 	f(i,lg)
  56. 	{
  57. 		if((1<<i) & k)
  58. 		{
  59. 			x=lca[x][i];
  60. 			if(x==-1)
  61. 				break;			
  62. 		}
  63. 	}
  64. 	return x;
  65. }
  66. void solve()
  67. {
  68. 	memset(adj,0,sizeof(adj));
  69. 	memset(lca,-1,sizeof(lca));
  70. 	int p,root;
  71. 	s(p);
  72. 	int x,y;
  73. 	f(i,p)
  74. 	{
  75. 		s(x),s(y);
  76. 		if(y==0)
  77. 			root=x;
  78. 		else
  79. 			adj[y].pb(x);
  80. 	}
  81. 	lca[root][0]=-1;
  82. 	dfs(root);
  83. 	int q;
  84. 	s(q);
  85. 	int val,k;
  86. 	while(q--)
  87. 	{
  88. 		s(val);
  89. 		switch(val)
  90. 		{
  91. 			case 0:
  92. 				s(x),s(y);
  93. 				addNode(x,y);
  94. 				break;
  95. 			case 1:
  96. 				s(x);
  97. 				delNode(x);
  98. 				break;
  99. 			case 2:
  100. 				s(x),s(k);
  101. 				int ans=getKthNode(x,k);
  102. 				if(ans==-1)
  103. 					printf("0");
  104. 				else
  105. 					p(ans);
  106. 				printf("\n");
  107. 				break;
  108. 		}
  109. 	}
  110. 	f1(i,N) 
  111. 		adj[i].clear();
  112. }
  113. int main()
  114. {
  115. 	int t;
  116. 	s(t);
  117. 	while(t--)
  118. 	{
  119. 		solve();
  120. 	}
  121. 	return 0;
  122. }
Success #stdin #stdout 0s 13928KB
comments (?)
stdin
copy 
2
7
2 0
5 2
3 5
7 5
9 8
8 2
6 8
10
0 5 15
2 15 2
1 3
0 15 20
0 20 13
2 13 4
2 13 3
2 6 10
2 11 1
2 9 1
1
10000 0
3
0 10000 4
1 4
2 4 1
stdout
copy 
2
2
5
0
0
8
0
https://ideone.com/ErsROj
language:
C++ 4.3.2 (gcc-4.3.2)
created:
3 years ago
visibility:
secret

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!