#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
int n,m,q,depth[100009],par[20][100009];
int timer=0,tin[100009],tout[100009];
int sz[100009],pre[100009],st[100009];
i64 BIT[500009];
pair<int,int> e[100009];
vector<int> adj[100009];
void DFS(int u,int pu,int d)
{
tin[u]=++timer; depth[u]=d;
for(int& v:adj[u])
if(v!=pu) DFS(v,u,d+1);
tout[u]=timer; par[0][u]=pu;
}
void update(int i,int v)
{
while(i<=n)
{
BIT[i]+=v;
i+=(i&-i);
}
}
i64 get(int i)
{
i64 r=0;
while(i>0)
{
r+=BIT[i];
i-=(i&-i);
}
return r;
}
int find_set(int u)
{
for(int i=19;i>=0;--i)
if(get(tin[par[i][u]])==get(tin[u])) u=par[i][u];
return u;
}
int main()
{
if(fopen("D:/CPP/THEMIS/test.inp","r"))
{
freopen("D:/CPP/THEMIS/test.inp","r",stdin);
freopen("D:/CPP/THEMIS/test.out","w",stdout);
}
ios_base::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
cin>>n>>m>>q;
for(int i=1;i<n;++i)
{
cin>>e[i].first>>e[i].second;
adj[e[i].first].push_back(e[i].second);
adj[e[i].second].push_back(e[i].first);
}
DFS(1,0,0); par[0][1]=1; fill(sz,sz+n+1,1);
for(int i=1;i<20;++i) for(int j=1;j<=n;++j)
par[i][j]=par[i-1][par[i-1][j]];
for(int i=1;i<=n;++i)
{
if(depth[e[i].first]>depth[e[i].second]) swap(e[i].first,e[i].second);
update(tin[i],1); update(tout[i]+1,-1);
}
for(int x,i=1;i<=m;++i)
{
cin>>x;
if(!st[x])
{
sz[find_set(e[x].first)]+=sz[e[x].second]-pre[x];
update(tin[e[x].second],-1); update(tout[e[x].second]+1,1);
}
else
{
sz[e[x].second]=pre[x]=sz[find_set(e[x].first)];
update(tin[e[x].second],1); update(tout[e[x].second]+1,-1);
}
st[x]^=1;
}
for(int x,i=1;i<=q;++i)
{
cin>>x;
cout<<sz[find_set(x)]<<'\n';
}
}
/*
........................
..::-+**#%@@@@@@@@@@@@@@@@@@%#**+::..
..:=++#%%@@@@@@@@@@@@@@@@%%%%%%%%%@@@@@@@@@@@@%+.
..:-+*#%@@@@@@@@%%%%##############################%%@@@@*:.
..:-+*%@@@@@@@%%%##########################################%@@@@+:.
..:=+%@@@@@@%%#####################################################@@@@+..
....-+%@@@@@@%#############################################################@@@@=..
..=#@@@@@%%###################################################################%@@@%-.
.:+#%@@@@%%#########################################################################%@@@#:.
.:=*%@@@%%###############################################################################%@@@@-.
..-*%@@@%%#####################################################################################%@@@=.
..+@@@@###########################################################################################%@@@*..
.*@@@#*##############################################################################################@@@%.
.+@@@#**################################################################################################@@@%:.
.-%@@#**####%##############################################################################################%@@%:.
.+@@#***###%%################################################################################################%@@@-.
:#@%****###%%*#################################################################################################%@@@-.
-@@%****###@%*###################################################################################################%@@@-.
-@@#***###%@#*#####################################################################################################%@@@=.
-@@#***###@@#*#######################################################################################################@@@%-.
:@@#***###@%**#########################################################################################################@@@+.
:%@#***##%@%**##########################################################################################################%@@@.
.#@%***##%@%**############################################################################################################%@@*.
.+@%***##@@#**##############################################################################################@@##############@@@:.
:@@***##@@#**###############################################################################################@@@%############%@@#.
.%@#***#@@#**####################################%@@%#######################################################@@@@@@############@@@=.
.*@%***%@@#***##################################%@@@@@@@%###################################################%@@@@@@@############@@%.
-@@***%@@#***##################################@@@@@@@@@@@%#################################################@@@@@@@@@###########@@@=.
.#@#**#@@#****################################%@@@@@@@@@@@@@@@%#############################################%@@@@@@@@@@###########@@%.
=@%**#@@%****################################@@@@@@@@@@@@@@@@@@@%###########################################@@@@@@@@@@@@##########%@@=.
.@@**#@@%*****##############################%@@@@@@@@@@@@@@@@@@@@@@@########################################@@@@@@@@@@@@@@##########@@%.
.#@###@@%*****##############################@@@@@@@@@@@@@@@@@@@@@@@@@@@#####################################@@@@@@@@@@@@@@@@#########@@@-
..#@###%@@******############################%@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@##################################%@@@@@@@@@@@@@@@@@#########@@#.
.-%@###%@@#*****############################%@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@###############################%@@@@@@@@@@@@@@@@@@@########@@@:.
...-%@%####@@#******###########################@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@%############################%@@@@@@@@@@@@@@@@@@@@%#######%@@*.
..:+%@@######%@%******###########################@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@%##########################@@@@@@@@@@@@@@@@@@@@@@%#######@@@.
.#@%%%##########@@*******#########################%@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@%######################%@@@@@@@@@@@@@@@@@@@@@@@@%######%@@+.
:#@%##########@@#******#########################@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@####################%@@@@@@@@@@@@@@@@@@@@@@@@@@#######@@%.
.+%@%#######%@%*******########################@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@%#################%@@@@@@@@@@@@@@@@@@@@@@@@@@@@######%@@-.
.+%@@%####@@#******#######################%@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@###############%@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@######@@#.
.:*%@@@@@%*******######################%@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@#############@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@%#####%@@:.
.....-@@********#####################%@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@%#########%@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@%#####@@*.
.=@%*******#####################%@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@#######@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@#####@@@.
.%@#*******####################@@@@@@@@@@@@@@@@@@@@@@@@@@%##*******##%@@@@@@@@@@@@@@@@@@@@@@####%@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@#####@@=.
.+@@********###################@@@@@@@@@@@@@@@@@@@@@@#*=:...............:=*#@@@@@@@@@@@@@@@@@@#%@@@@@@@@@@@@@@#*+-:.......:-=+#%@@@@@@@@@%####@@%.
.@@%*******###################@@@@@@@@@@@@@@@@@@@@#-.........................-*%@@@@@@@@@@@@@@@@@@@@@@@@@@%*-....................=#@@@@@@@#####@@=.
.+@@********##################@@@@@@@@@@@@@@@@@@@=...............................-%@@@@@@@@@@@@@@@@@@@@@@%-..........................=@@@@@@####@@%.
:@@@********#################@@@@@@@@@@@@@@@@@@=...................................-@@@@@@@@@@@@@@@@@@@@-..............................+@@@@%####@@+.
.*@@#********################%@@@@@@@@@@@@@@@@#:..........................:=+++=:....:*@@@@@@@@@@@@@@@@*:....:=+++=:.....................:%@@@####%@@:.
:@@@********################%@@@@@@@@@@@@@@@@*...........................=*#%%%#*=.....+@@@@@@@@@@@@@@=.....-*#%%%#*-.....................:#@@%####@@#.
.*@@%********###############%@@@@@@@@@@@@@@@@#...........................-*%@@@@@%*-.....*@@@@@@@@@@@@+.....-*%@@@@@#*-.....................:@@@####%@@*.
.=@@@*********###############@@@@@@@@@@@@@@@@@:...........................*=-@@@@@@#*.....:@@@@@@@@@@@@......*=+@@@@@@*+......................=@@@####@@@=.
-@@@**********##############@@@@@@@@@@@@@@@@@#............................*..+@@@@@#*......#@@@@@@@@@@*.....:*..#@@@@@#*......................:@@@%####@@@=.
.+@@@#**********#############%@@@@@@@@@@@@@@@@@*............................+-.%@@@@@*+......#@@@@@@@@@@+......*:.%@@@@@*+.......................@@@@#####@@@=.
.-%@@@***********##############@@@@@@@@@@@@@@@@@@#............................-*#@@@@@#*:......%@@@@@@@@@@+......=*#@@@@@#*:......................:@@@@%#####@@@+.
..=#@@@#************#############@@@@@@@@@@@@@@@@@@@@:............................-+*###*+:......:@@@@@@@@@@@#.......=*#%%#*+:.......................=@@@@@######@@@#.
...:=*@@@%#*************#############%@@@@@@@@@@@@@@@@@@@@*..............................:===:........#@@@@@@@@@@@@-.......:=++=-.........................%@@@@@@######@@@%-.
.-+*%@@@@%#****************#############@@@@@@@@@@@@@@@@@@@@@@=.........................................+@@@@@@@@@@@@@@:....................................#@@@@@@@#######%@@@*..
-@@%**********************#############%@@@@@@@@@@@@@@@@@@@@@@@+.......................................#@@@@@@@@@@@@@@@@:..................................#@@@@@@@@@########@@@@=.
.:%@%********************##############@@@@@@@@@@@@@@@@@@@@@@@@@%-...................................=@@@@@@@@@@@@@@@@@@@*...............................=@@@@@@@@@@@%########%@@@%+.
.+@@#******************##############@@@@@@@@@@@@@@@@@@@@@@@@@@@#=..............................:+%@@@@@@@@@@@@@@@@@@@@@%+:..........................=#@@@@@@@@@@@@@##########%@@@@*:.
.:%@@#****************#############%@@@@@@@@@@@@@@@@@@@@@@@@@@@@@%+-........................:=*@@@@@@@@@%%@@@@@@@@@@%@@@@@*-:....................-+@@@@@@@@@@@@@@@@%###########%@@@+.
.+@@%***************#############%@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@*=-:..............::-+#@@@@@@@%#+-:::-#@@@@@@#::-+#@@@@@#=-::.........::-=*@@@@@@@@@@@@@@@@@@@@##########%@@@+.
.#@@%*************#############@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@#*++++++*#%@@@@@@@@@@%=:::::::::::+@@@=:::::::-#@@@@@@@@@%%%%%@@@@@@@@@@@@@@@@@@@@@@@@@@@%########%@@@=.
.-%@@%************############@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@#=-:::::::::::::::-:::::::::::-=@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@%#######@@@@-.
..=%@@%**********############@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@+-:::::::::::::::::::::::::::::::::=%@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@######%@@@#:.
.=%@@%*********###########%@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@%=:::::::::::::::-+####=::::::::::::::::+@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@%######@@@@=..
.=%@@%#*******############%@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@%=::::::::::::::::+#+-::=#*::::::::::::::::-#@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@######%@@@%-.
.=%@@@#******#############%@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@+:::::::::::::::::*-:::::::*+:::::::::::::::::*@@@@@@@@@@@@@@@@@@@@@@@@@@@%######%@@@+..
.-%@@@%*****###############@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@#::::::::::::::::::-::::::::::=::::::::::::::::::=@@@@@@@@@@@@@@@@@@@@@@@@@#######@@@@:.
..-#@@@@#***################@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@=::::::::::::::::::::::::::::::::::::::::::::::::::-@@@@@@@@@@@@@@@@@@@@@@%######@@@@+..
.:+@@@@%#**################%@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@%-::::::::::::::::::::::::::::::::::::::::::::::::::::-@@@@@@@@@@@@@@@@@@@%######%@@@*:.
..=#@@@@#**################%%@@@@@@@@@@@@@@@@@@@@@@@@@@@@@#:::::::::::::::::::::::::::::::::::::::::::::::::::::::=@@@@@@@@@@@@@@@@%######%@@@#-.
.:*%@@@%###################%@@@@@@@@@@@@@@@@@@@@@@@@@@*:::::::::::::::::::::::::::::::::::::::::::::::::::::::::+@@@@@@@@@@@@@%#######@@@%=..
.-#@@@@%###################%@@@@@@@@@@@@@@@@@@@@@@*:::::::::::::::::::::::::::::::::::::::::::::::::::::::::-=@@@@@@@@@@@%######%@@@%=..
...-%@@@@@####################@@@@@@@@@@@@@@@@@@@@+::::::::::::::::::::::::::::::::::::::::::::::::::::::-#@@@@@@@@@@@%######%@@@%-..
...-#@@@@@%###################%@@@@@@@@@@@@@@@@@@@#+:::::::::::::::::::::::::::::::::::::::::::::::+%@@@@@@@@@@@%######%@@@@*:..
..:-*@@@@@@%%##################%@@@@@@@@@@@@@@@@@@%#+=:::::::::::::::::::::::::::::::::::::=*#%@@@@@@@@@@@%######%@@@@@#=..
..-+#@@@@@@%%##################%%@@@@@@@@@@@@@@@@@@%*+==-:::::::::::::::::::::::-=+*#%@@@@@@@@@@@@@%######%@@@@@*-:..
..=#%@@@@@@%%###################%@@@@@@@@@@@@@@@@@@@@@%#*+===------===+*#%@@@@@@@@@@@@@@@@@@%######%@@@@@%*-.
..-*@@@@@@@@@%####################%@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@%#######%@@@@@@#-..
.....=#@@@@@@@@@@%######################%%@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@%%########%@@@@@@%+:...
..::=*%@@@@@@@@@@%%#######################%%%%%@@@@@@@@@@@@%%%%############%@@@@@@@%=:..
...-=+#%@@@@@@@@@@@@%%%##########################################%%@@@@@@%*=-:..
...:-+*#%@@@@@@@@@@@@@@%%%%%#########################%%%@@@@@@@%*=:..
...*@@%@@@@@@@@@@@@@@@@@@@@@@@%%%%%%####%%@@@@@@@@%#+:..
.*@@****#####%%%@@@@@@@@@@@@@@@@@@@@@@@@@@@@#=:..
.@@%****##########@#====%%###@##@%%%@@@%-:....
-@@#****##########@#===+@#***@%=@%###@@%.
=@@*****##########%@===#@#***%@=%@###%@@-
.*@@*****###########@*==*%%%%%@@+@%###%@@+.
.@@%****############%@+=====++==%@#####@@%.
=@@#****#############@@========#@######@@@.
.*@@*****############@@%@+=====*@#######@@@=.
.%@@*****###########%@##@@#===#@########%@@*.
-@@%****###########%@%##@%%%*#@##########@@%.
=@@#****###########@%###@##%@@###########@@@-.
+@@*****##########@@###%@##%@@###########@@@+.
.%@@****##########@@####@%##%@@###########%@@%.
-@@%****#########@@#####@###%@@############@@@:
=@@#****########%@#####%@####@@############@@@=.
#@@*****#######%@######@%####@@############%@@#.
.%@@****#######%@######%@#####@@############%@@%.
-@@%****######%@#######%@#####@@%############@@@-.
=@@#****#####%@########@%#####@@%############@@@+.
+@@#****####%@########%@######@@%############%@@#.
.%@@****####%@#########@@######@@%############%@@@:
:@@%****###%@##########@%######@@%#############@@@=.
=@@%****##%%##########%@#######@@%#############@@@*.
#@@#****#%%###########@@#######@@@#############%@@%.
.%@@*****%############%@%#######@@@#############%@@@:
-@@@****##############@@########%@@##############@@@+.
-@@%****##############@%########%@@##############@@@#.
.*@@#****#############@@#########%@@##############%@@@:
.%@@*****#############@%#########%@@##############%@@@-.
:@@@*****############%@##########%@@###############@@@*.
-@@%*****############@%##########%@@###############@@@%.
#@@#****############%@############@@###############%@@@:
.%@@#****############@%############@@%###############@@@=.
:@@@*****###########%@#############@@%###############@@@*.
-@@%*****###########@%#############@@%###############@@@%.
=@@%*****##########%@##############@@%###############%@@@:
.#@@#*****##########@%##############@@%################@@@+.
:@@@*****###########@###############@@%################@@@#.
*/
Compilation message (stderr)
synchronization.cpp: In function 'int main()':
synchronization.cpp:45:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
45 | freopen("D:/CPP/THEMIS/test.inp","r",stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
synchronization.cpp:46:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
46 | freopen("D:/CPP/THEMIS/test.out","w",stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |