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.  

UVA 11838 - Come and Go

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef pair<int,int> pii;
typedef map<int,int> mi;

#define si(a) scanf("%d",&a)
#define sii(a,b) scanf("%d %d",&a,&b)
#define siii(a,b,c) scanf("%d %d %d",&a,&b,&c)
#define pi(a) printf("%d\n",a)
#define nl printf("\n");
#define pb push_back
#define mp make_pair
#define all(c) (c).begin(),(c).end()
#define f(i,a,b) for(i=a;i<b;i++)
#define rf(i,a,b) for(i=a;i>=b;i--)
#define clr(x,a) memset(x,a,sizeof(x))
#define MAX 1000100
#define MOD 1000000007
int c,n,m,vis[3000];
vector<int>vec[MAX];
void dfs(int x)
{
    vis[x]=1;
    c++;
    int i;
    for(i=0;i<vec[x].size();i++)
    {
        if(vis[vec[x][i]]==0)
            dfs(vec[x][i]);
    }
}

int main()
{
    int r,k,i,x=0,y=0,j,t,l,flag,x1=0,y1=0,z;
    ll ans=0;
    string p;
    while(1)
    {
        cin>>n>>m;
        if(n==0 && m==0)
            break;
        for(i=1; i<=m; i++)
        {
            cin>>x>>y>>z;
            if(z==1)
                vec[x].push_back(y);
            else
            {
                vec[x].push_back(y);
                vec[y].push_back(x);
            }
        }
        flag=0;
        for(i=1; i<=n; i++)
        {
            memset(vis,0,sizeof(vis));
            c=0;
            dfs(i);
            if(c!=n)
            {
                flag=1;
                break;
            }
        }
        for(i=1; i<=n+5; i++)
            vec[i].clear();
        if(flag)
            cout<<0<<endl;
        else
            cout<<1<<endl;
    }

    return 0;
}

LCA (Longest Common Anchestor)

///...................SUBHASHIS MOLLICK...................///
///.....DEPARTMENT OF COMPUTER SCIENCE AND ENGINEERING....///
///.............ISLAMIC UNIVERSITY,BANGLADESH.............///
///....................SESSION-(14-15)....................///
#include<bits/stdc++.h>
using namespace std;
int level[100005], parnt[100005];
vector<int>vec[100005];
int n;
void dfs(int u,int par,int depth)
{
    level[u]=depth;
    parnt[u]=par;
    for(int i=0; i<vec[u].size(); i++)
    {
        int v=vec[u][i];
        if(v!=par)
        {
            dfs(v,u,depth+1);
        }
        else
            continue;
    }
}
int dist[100005][20];
void lca_init()
{
    memset(dist,-1,sizeof(dist));
    for(int i=0; i<n; i++)
    {
        dist[i][0]=parnt[i];
    }
    for(j=1;j<20;j++)
    {
        for(i=1;i<=n;i++)
        {
            if(dist[i][j-1]!=-1)
                dist[i][j]=dist[dist[i][j-1]][j-1];
        }
    }
}
int lca(int x,int y)
{
    if(level[x]<level[y])
        swap(x,y);
    int power=1;
    while(1)
    {
        if(1<<(power+1)>level[x])
        {
            break;
        }
        power++;
    }
/// int power= log2(level[u]); eitao kora jai
    for(int i=power;i>=0;i--)
    {
        if(level[x]-(1<<i)>=level[y])
        {
            x=dist[x][i];
        }
    }
    if(x==y)
    {
        return x;
    }
    for(int i=power;i>=0;i--)
    {
        if(dist[x][i]!=-1&&dist[x][i]!=dist[y][i])
        {
            x=dist[x][i],y=dist[y][i];
        }
    }
    return parnt[x];
}
main()
{
    cin>>n;
    int u,v,i;
    for(i=1; i<n; i++)
    {
        cin>>u>>v;
        u--,v--;
        vec[u].push_back(v);
        vec[v].push_back(u);
    }
    dfs(0,0,0);
    lca_init();
    int q;
    cin>>q;
    for(i=1;i<=q;i++)
    {
        cin>>u>>v;
        u--,v--;
        cout<<lca(u,v)+1<<endl;
    }
}


/*
9    ///node no
1 2
1 3
2 4
2 5
5 7
5 8
8 9
3 6
5     ///query
7 9   /// lca of 7 9 is 5
7 8   /// lca of 7 8 is 5
4 7   /// lca of 4 7 is 2
4 8   /// lca of 4 8 is 2
9 6   /// lca of 9 6 is 1

Ouptut:
5
5
2
2
1

*/