DFS With Segment tree -

1. Problem Link:
2. https://codeforces.com/contest/343/problem/D

Mike wants to do the following operations with the tree:

1. Fill vertex v with water. Then v and all its children are filled with water.
2. Empty vertex v. Then v and all its ancestors are emptied.
3. Determine whether vertex v is filled with water at the moment. 

For each type 3 operation print 1 on a separate line if the vertex is full, and 0 if the vertex is empty. Print the answers to queries in the order in which the queries are given in the input.

Input:

5

1 2

5 1

2 3

4 2

12

1 1

2 3

3 1

3 2

3 3

3 4

1 2

2 4

3 1

3 3

3 4

3 5

Output:

0

0

0

1

0

1

0

1

1. ///...................SUBHASHIS MOLLICK...................///
2. ///.....DEPARTMENT OF COMPUTER SCIENCE AND ENGINEERING....///
3. ///.............ISLAMIC UNIVERSITY,BANGLADESH.............///
4. ///....................SESSION-(14-15)....................///
5. #include<bits/stdc++.h>
6. using namespace std;
7. #define sf(a) scanf("%d",&a)
8. #define sf2(a,b) scanf("%d %d",&a,&b)
9. #define sf3(a,b,c) scanf("%d %d %d",&a,&b,&c)
10. #define pf(a) printf("%d",a)
11. #define pf2(a,b) printf("%d %d",a,b)
12. #define pf3(a,b,c) printf("%d %d %d",a,b,c)
13. #define sfl(a) scanf("%lld",&a)
14. #define sfl2(a,b) scanf("%lld %lld",&a,&b)
15. #define sfl3(a,b,c) scanf("%lld %lld %lld",&a,&b,&c)
16. #define pfl(a) printf("%lld",a)
17. #define pfl2(a,b) printf("%lld %lld",a,b)
18. #define pfl3(a,b,c) printf("%lld %lld %lld",a,b,c)
19. #define nl printf("\n")
20. #define timesave ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
21. #define ll long long
22. #define pb push_back
23. #define MPI map<int,int>mp;
24. #define fr(i,n) for(i=0;i<n;i++)
25. #define fr1(i,n) for(i=1;i<=n;i++)
26. #define frl(i,a,b) for(i=a;i<=b;i++)
27. #define tz 100000
28. /*primes in range 1 - n
29. 1 - 100(1e2) -> 25 pimes
30. 1 - 1000(1e3) -> 168 primes
31. 1 - 10000(1e4) -> 1229 primes
32. 1 - 100000(1e5) -> 9592 primes
33. 1 - 1000000(1e6) -> 78498 primes
34. 1 - 10000000(1e7) -> 664579 primes
35. large primes ->
36. 104729 1299709 15485863 179424673 2147483647 32416190071 112272535095293 48112959837082048697
37. */
38. //freopen("Input.txt","r",stdin);
39. //freopen("Output.txt","w",stdout);
40. //const int fx[]={+1,-1,+0,+0};
41. //const int fy[]={+0,+0,+1,-1};
42. //const int fx[]={+0,+0,+1,-1,-1,+1,-1,+1}; // Kings Move
43. //const int fy[]={-1,+1,+0,+0,+1,+1,-1,-1}; // Kings Move
44. //const int fx[]={-2, -2, -1, -1, 1, 1, 2, 2}; // Knights Move
45. //const int fy[]={-1, 1, -2, 2, -2, 2, -1, 1}; // Knights Move
46. bool tree[1050000];
47. int start[500050],End[500050],cnt=0,pr[500050];
48. vector<int>vec[500050];
49. int ss,ee;
50. void dfs(int u,int par)
51. {
52. pr[u]=par;
53. start[u]=++cnt; /// start kokhon hoece
54. for(int i=0; i<vec[u].size(); i++)
55. {
56. int v=vec[u][i];
57. if(v!=par)
58. {
59. dfs(v,u);
60. }
61. }
62. End[u]=cnt; /// ending kokhon hoece
63. }
64. void init(int s,int e,int node)
65. {
66. if(s==e)
67. {
68. tree[node]=true;
69. return;
70. }
71. int lft=node*2;
72. int right=node*2+1;
73. int mid=(s+e)/2;
74. init(s,mid,lft);
75. init(mid+1,e,right);
76. tree[node]=true;
77. return;
78. }
79. bool Fill(int s,int e,int node)
80. {
81. if(s>ee||ss>e) /// baire porce
82. return false;
83. if(s==e)
84. {
85. tree[node]=false;
86. return true;
87. }
88. int lft=node*2;
89. int right=node*2+1;
90. int mid=(s+e)/2;
91. bool ret=false;
92. if(tree[lft])
93. ret|=Fill(s,mid,lft);
94. if(tree[right])
95. ret|=Fill(mid+1,e,right);
96. tree[node]=tree[lft]|tree[right];
97. return ret;
98. }
99. void Empty(int s,int e,int node)
100. {
101. if(s==e)
102. {
103. tree[node]=true;
104. return;
105. }
106. int lft=node*2;
107. int right=node*2+1;
108. int mid=(s+e)/2;
109. if(ss<=mid)
110. Empty(s,mid,lft);
111. else
112. Empty(mid+1,e,right);
113. tree[node]=tree[lft]|tree[right];
114. return;
115. }
116. bool qry(int s,int e,int node)
117. {
118. if(ss>e||s>ee) /// baire porce
119. return false;
120. if(ss<=s&&e<=ee)
121. return tree[node];
122. int lft=node*2;
123. int right=node*2+1;
124. int mid=(s+e)/2;
125. return qry(s,mid,lft)|qry(mid+1,e,right);
126. }
127.  
128. main()
129. {
130. timesave;
131. int n,u,v,i,dir;
132. cin>>n;
133. for(i=1; i<n; i++)
134. {
135. cin>>u>>v;
136. vec[u].push_back(v);
137. vec[v].push_back(u);
138. }
139. dfs(1,-1);
140. init(1,n,1);/// fill up with 1--- parameter hocce first position,last position,node no
141. // for(i=1;i<=n;i++)
142. // cout<<i<<" "<<tree[i]<<endl;
143. int q;
144. cin>>q;
145. for(i=1; i<=q; i++)
146. {
147. cin>>dir>>v;
148. ss=start[v],ee=End[v];
149. if(dir==1)
150. {
151. if(Fill(1,n,1))
152. {
153. if(pr[v]!=-1)
154. {
155. ss=start[pr[v]];
156. Empty(1,n,1);
157. }
158. }
159. }
160. else if(dir==2)
161. {
162. Empty(1,n,1);
163. }
164. else
165. {
166. if(qry(1,n,1))
167. printf("0\n");
168. else
169. printf("1\n");
170. }
171. }
172. }
173.  
174.