#include <bits/stdc++.h>
#define Tree int h,int l,int r
#define Left (h<<1),l,(l+r)>>1
#define Right ((h<<1)|1),((l+r)>>1)+1,r
#define F first
#define S second
using namespace std;
const int N=1e5+5;
int n,m,q,timer,depth;
int in[N],out[N],O[N],dep[N],ANS[N],last[N];
int v[8*N];
bool Bol[2*N];
vector < int > V[N];
void Dfs(int x,int p) {
dep[x]=++depth;
in[x]=++timer,O[in[x]]=x;
for (int i=0; i<V[x].size(); i++) {
int to=V[x][i];
if (to!=p) Dfs(V[x][i],x);
}
out[x]=timer,--depth;
}
void Build(Tree) {
if (l==r) {
v[h]=out[O[l]];
return ;
}
Build(Left),Build(Right);
v[h]=max(v[(h<<1)],v[((h<<1)|1)]);
}
int idx,type;
void Upd(Tree) {
if (idx<l || r<idx) return ;
if (l==idx && r==idx) {
if (type)
v[h]=-1;
else
v[h]=out[O[l]];
return ;
}
Upd(Left),Upd(Right);
v[h]=max(v[(h<<1)],v[((h<<1)|1)]);
}
int L,R,D;
int Get(Tree) {
if (r<L || R<l) return -1;
if (l==r) {
if (v[h]==-1) return -1;
return O[l];
}
if (L<=l && r<=R) {
int x=v[(h<<1)],y=v[((h<<1)|1)];
if (R<=y) return Get(Right);
return Get(Left);
}
int x=Get(Left),y=Get(Right);
if (x==-1) return y;
if (y==-1) return x;
if (R<=out[y]) return y;
if (R<=out[x]) return x;
return -1;
}
main () {
scanf("%d%d%d",&n,&m,&q);
vector < pair < int , int > > edges;
for (int i=1; i<n; i++) {
int a,b;
scanf("%d%d",&a,&b);
V[a].push_back(b);
V[b].push_back(a);
edges.push_back({a,b});
}
Dfs(1,1);
Build(1,1,n);
for (int i=1; i<=n; i++) ANS[i]=1;
int x,a,b,delta,id;
for (int i=1; i<=m; i++) {
scanf("%d",&x); --x;
a=edges[x].F,b=edges[x].S;
if (dep[a]<dep[b]) swap(a,b);
Bol[a]^=1;
if (Bol[a]) {
idx=in[a],type=1;
Upd(1,1,n);
L=1,R=in[a],id=Get(1,1,n);
ANS[id]+=ANS[a]-last[a];
}
else
if (!Bol[a]) {
L=1,R=in[a],id=Get(1,1,n);
last[a]=ANS[id];
ANS[a]=ANS[id];
idx=in[a],type=0;
Upd(1,1,n);
}
}
for (int i=1; i<=q; i++) {
scanf("%d",&x);
L=1,R=in[x],id=Get(1,1,n);
printf("%d\n",ANS[id]);
}
}
Compilation message
synchronization.cpp: In function 'void Dfs(int, int)':
synchronization.cpp:18:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i=0; i<V[x].size(); i++) {
~^~~~~~~~~~~~
synchronization.cpp: In function 'int Get(int, int, int)':
synchronization.cpp:56:13: warning: unused variable 'x' [-Wunused-variable]
int x=v[(h<<1)],y=v[((h<<1)|1)];
^
synchronization.cpp: At global scope:
synchronization.cpp:68:7: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
main () {
^
synchronization.cpp: In function 'int main()':
synchronization.cpp:86:15: warning: unused variable 'delta' [-Wunused-variable]
int x,a,b,delta,id;
^~~~~
synchronization.cpp:69:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d%d",&n,&m,&q);
~~~~~^~~~~~~~~~~~~~~~~~~
synchronization.cpp:75:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d",&a,&b);
~~~~~^~~~~~~~~~~~~~
synchronization.cpp:88:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d",&x); --x;
~~~~~^~~~~~~~~
synchronization.cpp:110:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d",&x);
~~~~~^~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
2680 KB |
Output is correct |
2 |
Correct |
6 ms |
2680 KB |
Output is correct |
3 |
Correct |
6 ms |
2680 KB |
Output is correct |
4 |
Correct |
6 ms |
2680 KB |
Output is correct |
5 |
Correct |
6 ms |
2680 KB |
Output is correct |
6 |
Correct |
9 ms |
2808 KB |
Output is correct |
7 |
Correct |
26 ms |
3704 KB |
Output is correct |
8 |
Correct |
25 ms |
3704 KB |
Output is correct |
9 |
Correct |
25 ms |
3704 KB |
Output is correct |
10 |
Correct |
313 ms |
12520 KB |
Output is correct |
11 |
Correct |
305 ms |
12528 KB |
Output is correct |
12 |
Correct |
258 ms |
17332 KB |
Output is correct |
13 |
Correct |
249 ms |
12388 KB |
Output is correct |
14 |
Correct |
186 ms |
11628 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
146 ms |
14448 KB |
Output is correct |
2 |
Correct |
147 ms |
14316 KB |
Output is correct |
3 |
Correct |
125 ms |
16108 KB |
Output is correct |
4 |
Correct |
117 ms |
16236 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
2680 KB |
Output is correct |
2 |
Correct |
6 ms |
2680 KB |
Output is correct |
3 |
Correct |
6 ms |
2680 KB |
Output is correct |
4 |
Correct |
6 ms |
2680 KB |
Output is correct |
5 |
Correct |
6 ms |
2680 KB |
Output is correct |
6 |
Correct |
8 ms |
2808 KB |
Output is correct |
7 |
Correct |
31 ms |
4344 KB |
Output is correct |
8 |
Correct |
304 ms |
17900 KB |
Output is correct |
9 |
Correct |
298 ms |
18152 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
306 ms |
17900 KB |
Output is correct |
2 |
Correct |
167 ms |
17260 KB |
Output is correct |
3 |
Correct |
179 ms |
17388 KB |
Output is correct |
4 |
Correct |
176 ms |
17388 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
2680 KB |
Output is correct |
2 |
Correct |
6 ms |
2680 KB |
Output is correct |
3 |
Correct |
6 ms |
2680 KB |
Output is correct |
4 |
Correct |
7 ms |
2680 KB |
Output is correct |
5 |
Correct |
8 ms |
2812 KB |
Output is correct |
6 |
Correct |
31 ms |
3832 KB |
Output is correct |
7 |
Correct |
406 ms |
13420 KB |
Output is correct |
8 |
Correct |
307 ms |
17896 KB |
Output is correct |
9 |
Correct |
306 ms |
13540 KB |
Output is correct |
10 |
Correct |
250 ms |
12776 KB |
Output is correct |
11 |
Correct |
204 ms |
15596 KB |
Output is correct |
12 |
Correct |
201 ms |
15596 KB |
Output is correct |
13 |
Correct |
192 ms |
17388 KB |
Output is correct |