fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. #define lli long long int
  4. #define phbk push_back
  5. #define mp make_pair
  6. #define F first
  7. #define S second
  8. vector<lli> v[200010],G[200010];
  9. lli S[4*200010],lazy[4*200010],A[200010],pa[200010][22],IN[200010],OUT[200010],depth[200010];
  10. lli tim=0,x=0;
  11. void dfs(lli node,lli parent,lli level)
  12. {
  13. 	depth[node]=level;
  14. 	A[++x]=node;
  15. 	IN[node]=++tim;
  16. 	pa[node][0]=parent;
  17. 	for(lli i=0;i<v[node].size();++i)
  18. 	{
  19. 		if(v[node][i]!=parent)
  20. 		{
  21. 			G[node].phbk(v[node][i]);
  22. 			dfs(v[node][i],node,level+1);
  23. 		}
  24. 	}
  25. 	OUT[node]=tim;
  26. }
  27. lli LCA(lli p,lli q)
  28. {
  29.     lli tmp,log;
  30.     if(depth[p]<depth[q])
  31.     {
  32.        	tmp=p;
  33. 		p=q; 
  34. 		q=tmp;
  35.     }
  36.     for(log=1;(1<<log)<=depth[p];log++);
  37.     	log--;
  38.     for(lli i=log;i>=0;i--)
  39.         if(depth[p]-(1<<i)>=depth[q])
  40.             p=pa[p][i];
  41.     if(p==q)
  42.         return p;
  43.     for(lli i=log;i>=0;i--)
  44.     {
  45.     	if(pa[p][i]!=-1 && pa[p][i]!=pa[q][i])
  46.         {
  47.         	p=pa[p][i];
  48. 			q=pa[q][i];
  49. 		}
  50. 	}
  51.     return pa[p][0];
  52. }
  53. lli query(lli node,lli start,lli end,lli pos)
  54. {
  55. 	if(lazy[node]!=0)
  56. 	{
  57. 		S[node]+=lazy[node];
  58. 		if(start!=end)
  59. 		{
  60. 			lazy[2*node]+=lazy[node];
  61. 			lazy[2*node+1]+=lazy[node];
  62. 		}
  63. 		lazy[node]=0;
  64. 	}
  65. 	if(start==end)
  66. 		return S[node];
  67. 	lli mid=(start+end)/2;
  68. 	if(pos<=mid)
  69. 		return query(2*node,start,mid,pos);
  70. 	return query(2*node+1,mid+1,end,pos);	
  71. }
  72. void update(lli node,lli start,lli end,lli l,lli r,lli v)
  73. {
  74. 	if(lazy[node]!=0)
  75. 	{
  76. 		S[node]+=lazy[node];
  77. 		if(start!=end)
  78. 		{
  79. 			lazy[2*node]+=lazy[node];
  80. 			lazy[2*node+1]+=lazy[node];
  81. 		}
  82. 		lazy[node]=0;
  83. 	}
  84. 	if(start>r||end<l)
  85. 		return;
  86. 	if(start>=l && end<=r)
  87. 	{
  88. 		S[node]+=v;
  89. 		if(start!=end)
  90. 		{
  91. 			lazy[2*node]+=v;
  92. 			lazy[2*node+1]+=v;
  93. 		}
  94. 		return;
  95. 	}
  96. 	update(2*node,start,(start+end)/2,l,r,v);
  97. 	update(2*node+1,(start+end)/2+1,end,l,r,v);
  98. 	S[node]=S[2*node]+S[2*node+1];	
  99. }
  100. int main()
  101. {
  102. 	lli n,q,a,b,lca,s,e,m,ans,in,out;
  103. 	char c;
  104. 	scanf("%lld",&n);
  105. 	for(lli i=1;i<=n-1;++i)
  106. 	{
  107. 		scanf("%lld%lld",&a,&b);
  108. 		v[a].phbk(b);
  109. 		v[b].phbk(a);
  110. 	}
  111. 	memset(pa,-1,sizeof(pa));
  112. 	dfs(1,-1,1);
  113. 	for(lli j=1;(1<<j)<=n;j++)
  114.         for(lli i=1;i<=n;i++)
  115.             if(pa[i][j-1]!=-1)
  116.                 pa[i][j]=pa[pa[i][j-1]][j-1];            
  117. 	scanf("%lld",&q);
  118. 	while(q--)
  119. 	{
  120. 		cin>>c;
  121. 		if(c=='Q')
  122. 		{
  123. 			scanf("%lld",&a);
  124. 			printf("%lld\n",query(1,1,n,A[IN[a]]));
  125. 		}
  126. 		else if(c=='M')
  127. 		{
  128. 			scanf("%lld%lld",&a,&b);
  129. 			lca=LCA(a,b);
  130. 			update(1,1,n,A[IN[a]],A[OUT[a]],1);
  131. 			update(1,1,n,A[IN[b]],A[OUT[b]],1);
  132. 			if(depth[b]<depth[a])
  133. 				swap(a,b);
  134. 			if(lca==a)
  135. 			{
  136. 				s=0;
  137. 				ans=-1;
  138. 				e=G[a].size();
  139. 				while(s<=e)
  140. 				{
  141. 					m=(s+e)/2;
  142. 					in=IN[G[a][m]];
  143. 					out=OUT[G[a][m]];
  144. 					if(in>IN[b])
  145. 						e=m-1;
  146. 					else if(out<OUT[b])
  147. 						s=m+1;
  148. 					else
  149. 					{
  150. 						ans=m;
  151. 						break;
  152. 					}			
  153. 				}
  154. 				update(1,1,n,A[IN[ans]],A[OUT[ans]],-1);
  155. 			}
  156. 		}
  157. 		else
  158. 		{
  159. 			scanf("%lld%lld",&a,&b);
  160. 			lca=LCA(a,b);
  161. 			update(1,1,n,A[IN[a]],A[OUT[a]],-1);
  162. 			update(1,1,n,A[IN[b]],A[OUT[b]],-1);
  163. 			if(depth[b]<depth[a])
  164. 				swap(a,b);
  165. 			if(lca==a)
  166. 			{
  167. 				s=0;
  168. 				ans=-1;
  169. 				e=G[a].size();
  170. 				while(s<=e)
  171. 				{
  172. 					m=(s+e)/2;
  173. 					in=IN[G[a][m]];
  174. 					out=OUT[G[a][m]];
  175. 					if(in>IN[b])
  176. 						e=m-1;
  177. 					else if(out<OUT[b])
  178. 						s=m+1;
  179. 					else
  180. 					{
  181. 						ans=m;
  182. 						break;
  183. 					}			
  184. 				}
  185. 				update(1,1,n,A[IN[ans]],A[OUT[ans]],1);
  186. 			}
  187. 		}
  188. 	}
  189. }
Success #stdin #stdout 0s 77760KB
comments (?)
stdin
copy 
5
1 2
1 3
2 4
2 5
9
Q 1
M 3 5
Q 1
Q 3
M 1 4
Q 3
Q 4
D 3 5
Q 3
stdout
copy 
0
0
1
2
1
1
https://ideone.com/1Ou6WQ
language:
C++14 (gcc 8.3)
created:
6 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!