#include <bits/stdc++.h>
using namespace std;
const int maxn=1e5+10;
const int maxlog=20;
#define ll long long
struct fenwick{
ll* arr;
int size;
fenwick(int v){
int n=v;
arr= new ll[n+1];
size=n;
for (int i=0;i<=n+1;i++) arr[i]=0;
}
fenwick(vector<int>& v){
int n=v.size();
arr = new ll[n+1];
size=n;
for (int i=0;i<n;i++){
arr[i+1]=v[i];
}
build();
}
void build () {
for (int i=1;i<=size;i++){
int j= i + (i & (-i));
if (j<=size)arr[j]+=arr[i];
}
}
void update(int i,int delta){
for (;i<=size;i += i&(-i))arr[i]+=delta;
}
ll query(int i){
ll soma=0;
for (;i;i-= i &(-i))soma+=arr[i];
return soma;
}
ll query(int l,int r){
if (l==1)return query(r);
return query(r)-query(l-1);
}
};
int beg[maxn];
int en[maxn];
int ddepth[maxn];
int tempo=0;
int pai[maxn];
int dp[maxn][maxlog];
vector<int>grafo[maxn];
void dfs(int u,int p,int cc=0){
ddepth[u]=cc;
dp[u][0]=p;
for (int i = 1; i < 20 ; i++) {
dp[u][i] = dp[dp[u][i - 1]][i - 1];
}
tempo++;
beg[u]=tempo;
for (auto k:grafo[u]) if (k!=p) dfs(k,u,cc+1);
en[u]=tempo;
}
fenwick f(maxn);
void updt(int u,int i){
//cout<<beg[u]<<" : "<<en[u]<<endl;
f.update(beg[u],i);
f.update(en[u]+1,-i);
}
int getpar(int u){
int teste = u;
for (int i = 19; i>=0; i--) {
if (f.query(beg[dp[teste][i]]) == f.query(beg[u])) teste = dp[teste][i];
}
return teste;
}
pair<int,int> edge[maxn];
vector<int> isset(maxn,false);
vector<int> ans(maxn,1);
vector<int> lazyness(maxn,0);
void add(int ind){
auto u=edge[ind].first;
auto v=edge[ind].second;
if (ddepth[u]>ddepth[v]) swap(u,v);
ans[v]= ans[getpar(u)];
lazyness[v]=ans[getpar(u)];
updt(v,1);
}
void rem(int ind){
auto u=edge[ind].first;
auto v=edge[ind].second;
if (ddepth[u]>ddepth[v]) swap(u,v);
ans[getpar(u)]+=ans[v]-lazyness[v];
updt(v,-1);
}
int main(){
cin.tie(NULL);cin.sync_with_stdio(false);
int n,m,q;cin>>n>>m>>q;
for (int i=1;i<n;i++){
int a,b;cin>>a>>b;
grafo[a].push_back(b);
grafo[b].push_back(a);
edge[i]={a,b};
}
dfs(1,0);
for (int i=1;i<=n;i++) updt(i,1);
//for (int i=1;i<=n;i++) cout<<f.query(beg[i])<<" ";
//cout<<endl;
// updt(2,1);
//for (int i=1;i<=n;i++) cout<<f.query(beg[i])<<" ";
//cout<<endl;
//cout<<1<<endl;
while(m--){
int a;cin>>a;
if (isset[a]){
add(a);
}
else{
rem(a);
}
isset[a]=!isset[a];
}
while(q--){
int a;cin>>a;
cout<<ans[getpar(a)]<<endl;
}
}
Compilation message
In constructor 'fenwick::fenwick(int)',
inlined from 'void __static_initialization_and_destruction_0(int, int)' at synchronization.cpp:71:15,
inlined from '(static initializers for synchronization.cpp)' at synchronization.cpp:140:1:
synchronization.cpp:18:40: warning: 'void* __builtin_memset(void*, int, long unsigned int)' forming offset [800088, 800095] is out of the bounds [0, 800088] [-Warray-bounds]
18 | for (int i=0;i<=n+1;i++) arr[i]=0;
| ~~~~~~^~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
4556 KB |
Output is correct |
2 |
Correct |
3 ms |
4556 KB |
Output is correct |
3 |
Correct |
3 ms |
4640 KB |
Output is correct |
4 |
Correct |
3 ms |
4556 KB |
Output is correct |
5 |
Correct |
3 ms |
4684 KB |
Output is correct |
6 |
Correct |
6 ms |
4804 KB |
Output is correct |
7 |
Correct |
21 ms |
5964 KB |
Output is correct |
8 |
Correct |
21 ms |
5972 KB |
Output is correct |
9 |
Correct |
21 ms |
5964 KB |
Output is correct |
10 |
Correct |
247 ms |
17652 KB |
Output is correct |
11 |
Correct |
262 ms |
17656 KB |
Output is correct |
12 |
Correct |
322 ms |
23788 KB |
Output is correct |
13 |
Correct |
116 ms |
17944 KB |
Output is correct |
14 |
Correct |
149 ms |
17536 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
138 ms |
20880 KB |
Output is correct |
2 |
Correct |
128 ms |
20680 KB |
Output is correct |
3 |
Correct |
130 ms |
23752 KB |
Output is correct |
4 |
Correct |
128 ms |
23748 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
4556 KB |
Output is correct |
2 |
Correct |
4 ms |
4556 KB |
Output is correct |
3 |
Correct |
4 ms |
4556 KB |
Output is correct |
4 |
Correct |
5 ms |
4684 KB |
Output is correct |
5 |
Correct |
3 ms |
4556 KB |
Output is correct |
6 |
Correct |
7 ms |
4812 KB |
Output is correct |
7 |
Correct |
43 ms |
6548 KB |
Output is correct |
8 |
Correct |
540 ms |
23920 KB |
Output is correct |
9 |
Correct |
552 ms |
24060 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
540 ms |
23928 KB |
Output is correct |
2 |
Correct |
390 ms |
24344 KB |
Output is correct |
3 |
Correct |
377 ms |
24392 KB |
Output is correct |
4 |
Correct |
364 ms |
24360 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
4556 KB |
Output is correct |
2 |
Correct |
3 ms |
4556 KB |
Output is correct |
3 |
Correct |
3 ms |
4556 KB |
Output is correct |
4 |
Correct |
3 ms |
4556 KB |
Output is correct |
5 |
Correct |
6 ms |
4684 KB |
Output is correct |
6 |
Correct |
41 ms |
6092 KB |
Output is correct |
7 |
Correct |
495 ms |
17952 KB |
Output is correct |
8 |
Correct |
558 ms |
24004 KB |
Output is correct |
9 |
Correct |
343 ms |
18364 KB |
Output is correct |
10 |
Correct |
359 ms |
18268 KB |
Output is correct |
11 |
Correct |
348 ms |
21456 KB |
Output is correct |
12 |
Correct |
361 ms |
21412 KB |
Output is correct |
13 |
Correct |
375 ms |
24412 KB |
Output is correct |