//********###############***************+*******#####################*********************###**************#######****************+++++++****************+++
//********##############*****************+******#################**##*******++*******************+*+*******#######****************+++++++++***************++
//*******###############*****************+******#################**#********++******+***********+*++********#*####****************+++++++++***************++
//******###############*************************###*#############***#*******++******+***********+++++++****************************++++++++***************++
//*****#################************************##**##***#######****#*****+*++******+*+****+++====+++*******************************+++++++***************++
//*****##################***********************###*******#######*****+++++++=*****+=*+++++*++++==------==+++***********************++++******************++
//*******################********##************####*******#*###******+++++++==+****+-+-=+==-::..........:::::--+*****************************************+++
//**+*******#############*****#*####***********######****###*+-:..:.......::--=--=+=:+*=-::..........::::::::::::-+*************************************++++
//+++++******########********##**###***********#*#***###+-...::::::::::::::::::::::::::::..........::::::::::::-:::-=***#********************************+++
//+++++******########************##************##**#+-....::...::::::.::::::---:::::::::........:...::::--==----:::::::=*#**********************************
//+++++******#######**************#***************-..........::::::::----------=+=-::---:::::::::::::::::::--=++++==-::::-+=+*******************************
//++++******######**********#*************++++=:..........:::::::::::::::::::-===+-:+--:::::.........::-----:----==+*+-::-+**++**************+++**++******
//*+++*******#####***********#***********++++=:.:......::::--::::::::::::------=**++#*=-==----:::::::.::.:::-==-------=++-:::+*+++***********++++++++++**+++
//**++*******######********##*************+-::::....:::::-=::::::::::-----=-===:*#+#%*+*+==-----:::::::::-=-::--==-:----=+*=::-+++++*********+++++++++++++++
//**++*+******#####*********##**********+:::::::::---:-==::::::::-:----====+=+++++*%+=#*+++=----:::::::::::-==----==-------+*+:.-+++********++++++++++++++++
//**+++++*****#####******************#+-:-----:-=--:-==::::::::::---===+*###**+***#*=*#*==----:::::.::::-=----+=:=:-===--===-**=::+*++******++++++++++++++++
//***++++*****#####*****#######*****=::-------=+--=+-::::::::::-:--==+*###%%%##%#+#*-**=-------===-::::::---=-+*+-==:-=+=-=++-=**-.-++*+**++++++++++++++++++
//***+*******######****#########**+::----==-=++-=*+:--:::::::::--===+**+*=#%%%%%##%+=#+--+###+=:----::::---:-=-+*++++---=+==++=-+*+::++*++++++++++++++++++++
//**+*******#######***#########**+:---=++--++=-+*+---:::::::::-====++*#%%%*@%%%%*%#==+++*===+*##+--=::-+-----=+-+*+**+=-==+===+=-=*+::++++++++++++++++++++++
//*+++******#######***#######***+::--=+=-=++=+*+=:--::::::::-----=+++*#%%%*%%%#*#%#==+==----:::-=--+*--=+==-==+==*****+=-=++===++=-++-:=++++++++++++++++++++
//+++++****######******####****-::-==++=++++**+=-=-::--:::---:--==******#######*#%#=+***++=-::::::--====+====+++==***+++===+++==++===+=-==++++++++++++++++++
//++++++***######************+-:--=+++==+++**++==-::--------:--==++**########****#*+*#****#*+=--::----==++==+++++=+*#**+++==+===++====+=--==++++++++++++++++
//++++++***######*********++=:---=+===++++***++==---==---=:-:--=+++#%%%%%%%%%%#*++*###########+===----===++=++++++=+###**++==++==++====+=-===+*+++++++++++++
//+++++****#######*******++----===+==++++***++++--====--===---==***%%@@@@@%%@%##***###%%%%%%%%#*=====-====+++++**++=+#%#*#*+==++==++===++==++==*****++++****
//+++++****#######******++--====+++++**++****++=-=*==--===+--==+#%%@@@@@@%%%%%%#**####%%%%%%%%%#+=+++===++++++*+**+++*#####*+==+==++====++==++==+##*********
//++++*****########******-=====++++++*****+**++==*+==--==++-==+#%@%@@@@@%%%%%%###*#####%%%%%%%%%*++++=+=+++++++*+**+++*#####*+=====++====*+=-===--=****##***
//++++****#########*****==+++=+++++++*******++=+**++=-=++++=++#%%%@@@%%%####*******####%###%%%%#*++*++++++++*++++**+++*#%%###*+====+++===+++=-------+*******
//++++*****#########****=++++=+++*+********++++*++++===+++=+*#%%%%%%###*+++++++====++********###*****++++*+***++*****++*%%###**=====+++=+=+++==-----=*##****
//++++*****#########**#+=+++++**++**********+++*++*===+*+++**#%%####***+=====--------=====++******#*++****++*#*+*****++*#%%#%#*+==+=+++=+==++==----=+****#**
//+++*****##########**#+++++++++*****#*****+++*++++===+++++*##%%###**+===------:::::----====+++*****++*******#*++**+****###%##**+=+==++=++++++=====+++====-:
//****########*#######*++++++++****##+*****++**++*++++++=+***####**++=------::::::::::-----===++****+********##++##**#**##%%##**+=++=+*++++++++======----:::
//****################*+*++*++******+******++*++**++++**+**#*****+++==---::::::::::::::::----===++******#****##**##**##*##%%%#***+++=+*++++++=+=--==-::::::.
//***########*####%%%%#+*+*+++*******##*##*++*++**++*******#****+++===---:::::::::::::::::----==++****#*##*##*##*###*##**#%%%%#**+++++**+++*++==-:-=-::.....
//***########*###%%%@@%+#****+**+***###*#**+**+****+*******#****++====--::::::::::::::::::::---==+**#***############**#**#%%%%*#*++*+***++*#*++=-:.:-:......
//****######**##%%@@@@@*#****++****######******#***+**+****#***++===-----:::::::.....:.::::---==+**##*####################%%%%##*++*****+++##*++-::.:-:.....
//****##*###**##%%@@@@@*#**++***#*###*###****###********#***#**++====-----:::::::::::::::-----=++*###*####################%%%###*++*****+++*#*++=::..::.....
//*******#######%%@@@@@%*#*+++****#*#####****######**#*##***#*+====-----:::::::::...::::::---===+*########%####%##########%%####*++*#****++*#**++-.....:....
//*******###*###%%@@@@@%#*+**+*#*###%%###**#############****##*++========------::::::::::::----=+*#######%%%###%#######%%#%%####*++##********##*+=..........
//********######%%@@@@@%%****+*#*########**#####*########*+*#*+=-----:::::::::::::::::::::::---+*##**#*####%###%#######%%#%%####*+*###*#******#*++:...::::::
//********##*###%%@@@@@%@#***+***#%#%%%%#**######%%#####**+***+==------::::::::::::..::::::::-=*###**#*########%######%%%#%%%%##***#%#*********#*+-..:::::::
//********###*##%%@@@@@@@%#**+***##%%%%%#**#####%%#######***###********+==-::::::::::::::::::-*######%#%%%%%%%%%%#####%%%#%%%%##***%%#*****##*+***=:::::::::
//*******###**##%@@@@@@@@%*#*****###%%%%*#*#####%%%#######*########%%%###+===-:::::::::::::--=*#%%%%%%%%%%%%%%%%%%#####%%%%%%%##***%%#*****##*++*++:::::::::
//*******#######%%@@@@@@@####*+**###%%%%####%##%%%%#########*##****+*++++=====-::::::::::--=+**##%%%%%%%%%###%%%%#######%%%%%%##**##%#*#***##**++**-::::::::
//***#######*###%%@@@@@@%%##*++**###%@%%#%##%#%%#%####*#%###++**+++=====----=--:::::::::--==+++**#%###%%%##*###%%%######%%%%%%#**###%%##***###*++**-::::::::
//***#######*###%%@@@@@@%%%#*++*+##%%%%#*#####%%%%#*****####*=+*++++=====------:::::::::---======+*####%%%#**#####**#####%%%%%#####%%%##**#####*=+*-:-------
//**########*##%@@@@@@@%%%##++*+###%%%####%%%%%%%###**++**##*+**+++=========---::::::::------====+++**#%%%%%#####***####%%%%%#####%%%##*######*=*:--------
//***#######**##%@@@@@@@%%%%#*+***##%%%#%#%%%%%%%%#***+==+#*##*****+++===++===---::::::------========+++**#####%%##*****##%%%%#####%%%##**#%%##*+*=:::------
//***#######**##%@@@@@@@%%%%#*****##%%%%%#%%%%#%%%#**++=-=**####*#*+++++++++++==--:::::---=======+++++++****+++++*##******%%%####%#%%%##*##%%##*++::::------
//***######***##%@@@@@@@@@%%%*****######%%%%%%#%%##**++===+####%%%%%%%%#*++++++=--:::::---==++++++*%%@@%%##*+++====+**++++*%%%%##%%%%%##*#%%%%#*+-:-:-------
//***######**###%@@@@@@@%@%%%#**#**##%%%@#%%#%%%##**+====++*##%#*#%%%*##***+++++=-::::::--=++++*#*+#%#*#*=+#**++=----=====+#%%%%#%%%%%####%%%##+=-----====--
//***######**###%%@@@@@@%@%%%#**###*%##%%###%%%##*++=======+**##**#%%%#++*##==++=-::..::-==+==*#*+=#%###*+*++++==--------==+#%%%%#%%%####%#%%#*==-=-======-:
//***######**###%%%@@@@@@@%%%%**%%%######*####**++==--------=+***++=======----==-::....:--======+++++====-----------:::::--=*%%%%##%%%%%%%#%%#+=+=====----::
//***######***##%%%@@@@@@@%%%%#*#%%##%%%#**#%%*====--:-::----=***++==+++===------:.....::-----==========--------::::::::::--+%%@%##%%%%%%##%%*++**+==---::::
//**######***###%%@@@@@@@@%%%%######%%%%%%%%%#+---:::::::::--=+========-----:---::.....::----:----========----:::::::::::::-=#%%%#%%##%%%##%#****#*+==-:::::
//**#######**###%@@@@@@@@%%%%%%##**##%%%%%%%##+=-::....::::-------------::::::-:::......::-:::::::::::-:::::::::::::::::::::-+%%%%%%%%%%#%%#*####%%%%#=-::::
//**######***###%@@@@@@@@%%%%%%%#**####%##%%%#*=::........:::::::::::::::::::::::.......:::::::::::::::::::::::::::::::::::::=%%%%%%%###%%####%%@@@@@@@*=---
//**#######**###%@@@@@@@@%%%%@%%%#***+*####%%%*=:...........:::::::::::::::::::::.......:::::::::::::::::::::::::::::::::::::=#%%#%%%%#####%%%%@@@@@@@@@@%%@
//**#######**##%%@@@@@@@@%%%%%%@@%##*##**#####*-:..................:::::::::::::.........::::::::::::::::::::::::::::::::::::-#%#*%##%####%@@@@@@@@@@@@@@@@@
//**#######**###%@@@@@@@@%%%%@@@@@@%####******+:::....................:::::::::...........::::::::::..:::::::.:::::::::::::::-*+=*%##%##%%%@@@@@@@@@@@@@@@@@
//**###*##***###%@@@@@@@%%%%%@@@@@@@%%###**++*+::..................::::::-::::.............::::::-::::::::::::::::::::.::::::-+===*#####@@@@@@@@@@@@@@@@@@@@
//+**********###%@@@@@@@@%%%%@@@@@@%%%##***+=++::...............:::::::--::................::...::---::::::::::::::::::.:::::-+=-=#####%@@@@@@@@@@@@@@@@@@@@
//+**********###%@@@@@@@%%%%%%@@@@@@%###%##*==+:::::.......::::::::::---:.....::.......:::::::...::----::::::::::::::::::::::-+=*%%%%%%#@@@@@@@@@@@@@@@@@@@@
//+**********###%@@@@@@@%%%%%%@@@@@@@%%%%#**+++-::::..:::::::::::::-----::::::::::::::::::::::::::---=----:::::::::::::::::::-*=*@%@@@@%%@@@@@@@@@@@@@@@@@@@
//****####***##%%@@@@@@@%%%%%%@@@@@@@@%%%##*++*=::::::::::::::::::----------==-------:-----=++=-------==----:::::::::::::::::+++%@@@@@@@@@@@@@@@@@@@@@@@@@@@
//.......::---=++*###%%%####*####%%%%%%%%#%#+=**:::::::::::::-------------==+****==-----=+++=====------===----::::::::::::::-*+#@@@@@@@@@@@@@@@@@@@@@@@@@@@@
//..............................::::::::::::-=**=::::::-------------------==+===++++======--==----:::---===-------::::::::::+###@@@@@@@@@@@@@@@@@@@@@@@@@%%*
//...........................................:-==:::::----------------::::--========+++===-------:::::---====-------:::::::=###+*####%%%%%%%@@@@@@@@@@@%*==-
//............................................::.:::::----------------::::::----========-------::::::::----==------:::::::-*%##*=---------===--:::::::::::::
//............................................::::-:::----------------::::::::::::---------:::::::::::::----=------::::::-*%%###+-::....:::::::.........::::
//::::::::::::::..::..:...:::..................:.:+=::-------------=--:::::::::-================--:::::::--------::::::::=%@%###*=::......................::
//------------------------------------::::::::.::-*%=--------------------=++++***++***++++*+=+*++*+++=---:-----::::::::--#####%##+::.......:::...........:::
//********++++***###******+++++++++++++++==-:::::-*%%=--------------==#%%*===--=-:::--::::-::-::---+#%*-------:::-------#%%#*****+-:::.:...:::::::::::::::::
//###########%%%@@@@@@@@@@@%%%%%%%%@@@@@@%*+=-:::--=**=-------------=+#@%%%%%*=+=:::--::.::::--:+#%@@#=---:--:::-------#%####***+==-::::::::::::::::::::::::
//--===+=++++++***####%###########%%%%%%%%#+=-:::.::------------------+%@%%@@@@@%%%%%%####%%%@@@@@@%*=----::::--------=@%*****++==+==------:::::::::::::::::
//-----------======++====-========++++++++==-:::..:--::----------------+#%%%@@@@%####%%###%%%@@@@@#+=::::::-----------+@%#+*###*+==++========---::::::------
//::-----------=======-------============-:.....::::.:-=+=----------:---=+#%@@@@%##########%%@@@%*+=-::::::::---------*@%#**####*+==+++++===++++==-----=====
//::-==--------==-===-------==+====+++=:......:::::.::-+*#=---------:::---=#@@@@%##*########%@@%+==-:::::::::---------%@##***#%##*+========+==+*****+==-----
//--*#########%@@@@@@@+=====*#%%#*=-:...:::::::::::.:-=+*%#=--------:::--=--+#@@%#**####**##%%*+==-::::::::::--------=%%##***#%%##*=+**+***+++=-::-==++++++=
//--*#**#######%@@@@@@#-======-::::...::===-::::::::--==+#@%=------:::::----:-+#%##**##*###*+====-::::::::::::::-----*@%##***#%%%##+=+*+*******++*#*+=------
//--*####****%%@@%*=:.:--::::::..:::::--=++-::::::::-=-=+#@@%=-----::::::-=-----=+*####*=--==-==-::::::::::::::-----+%@%##***#%%%%##++**###****#*+*#%%%%##*+
//--*######*=:::-=+##*-::......:--:-====+++=-::::::-=--=*%@@@%=----:::::::-===--------------===-::::::::::::::----==*@@%##**##%%%%%#*+++*#########*+++==++++
//--*%#=:.-+#%%##*=:......::.:--:::-----=++=-:::::-----+#@@@@@%=---:::::::--=+===--------==++=--:::::::::::::---===+%@@%##**##%%%%%##******###***##**###*+==
//=+:.:+#%###*#+:.......::::-=-:::::::--==+=-:::::----=*%@@@@@@#=--::::::----=+++++++++++++=----::::::::::::--====+#@@@%##**###%%%%##*********+++*%%*=*%@@@@
//.:*%%%####+:...:::......-+-::::::--::-====-::::-----+#@@@@@@@@#=-:::::::-----===+++===-------::::::::::::--====+*%@@@%######%%%%%%##*##*****+**#*#%%*=*+=+
//%%%%%%#=...:-::...-::.=%=.:--::::-::::-===-::::=-:-=#%@@@@@@@@%*=-::::::::-=----==-==--------:::::::::::--====++#@@@%#######%%%%%%##*#****+***#%%##%%*+#%#
//@%@%-.::::...:+%@*:.+%-.:--------:::::-===-:::-=---+%%@@@@@@@@%#**-::::::::---=-=------------:::::::::-======++#@@@@%#######%%%%%%%##********##%%%###%%=+%
//+:.......=%%+:....=%+.:==----------::--===-:::----=#%%@@@@@@%%%%*+*=::::::::---------------:::::::::-=======++*%@@@@#######%%%%%%%%%#*******##%%%###**#%#-
//::..-*%*-......:*%=.:=+------------:::-===--:-----*#%@@@@@@%%%%%%**++=:::::::::----------::::::::::-=======++*#@@@@@#######%%%%%%%%%%#******#%%%#####%#*#%
//:*%#-........-#%=..-==-------------:::====-------=*#%@@@@@%%%%%%%#*++++=--::::::---------:::::::--=+++===+++*#%@@@@%#######%%%%%%%%%%###***##%%%########*+
//+:........:=%%=::--===------------:::-===-----=-=+#%%@@@@@%%%%#####*+++++=---------------------===+++++++++*#%%@@@@%######%%%%%%%%%%#%%%###%%%%%#########*
//.......:+#%%+:----===--:::-------::::--------===++#%%@@@@@%#########*++++*++===------==========+++++++++++**#%%%@@%######%%%%%%%%%%###%%%%%%@%%%##********
//:...::*@%#+:::--==---:::::------::::::-----=====+*#%%@@@@@%##########*++++****+++++++++++++++++++++++++++**#%%%%@@%####%%%%%%%%%%%%###%%%%%%%%%%##********
//...:#%-.::-:::----:::::::::::::::::::--=--====++**#%%@@@%%%###########*+=+++**++++++++++++++++++++++++++**##%##@@@%%%%%%%%%%%%%%%%%###%%%%%%%%%##*********
//:..::*@#-.:-=::::::::.::::::::::::::-----=====++*#%%@@@@%%%#############*++++***+++++++++++++++++++++++**##%%#%@@@%%%%%%%%%%%%%%%%###%%%%%%%%%####******#%
//::::--%@@%-.:-+=::::......::::::::::---======++**#%%@@@@@%@*#######%#*##**+==+++*+*++++++++*******+++++**#%%##@@@@%%%%%%%%%%%%%%%%####%%%%%%%#********#%%+
//---==+#%%@@@=..-+=:......:::::::::::-==-===+++**#%%%@@@@@%@#*%#####%##***#*+===++++*************++++++**%%%#*%@@@@%%%%%%%%%%%%%######%%%%%%%##******#@#++*
//==++*###%%@@@@=..:-+-:.:.::::::::::-==-==+++++**#%%@@@@@@@@@*%######%#******+==++++++++****++++++++++**%%%#*#@@@@@%%%%%%%%%%%########%%%%%###*****%@#++*%@
#include <bits/stdc++.h>
using namespace std;
#define ll long long
ll n,u,v,f[500005],par[500005],h[500005],k,ans,d[500005];
vector<ll>a[500005],vc[500005];
ll getlab(ll i)
{
if(f[i]<0)
return i;
return f[i]=getlab(f[i]);
}
void connect(ll u,ll v)
{
u=getlab(u);
v=getlab(v);
if(u==v)
return;
f[u]+=f[v];
f[v]=u;
return;
}
void dfs(ll x,ll pa)
{
par[x]=pa;
for(ll it:a[x])
if(it!=pa)
{
h[it]=h[x]+1;
dfs(it,x);
}
}
void collab(ll x,ll y)
{
x=getlab(x);
y=getlab(y);
while(x!=y)
{
if(h[x]<h[y])
swap(x,y);
connect(par[x],x);
x=getlab(par[x]);
}
return;
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
cin>>n>>k;
for(int i=1;i<=n;i++)
{
f[i]=-1;
cin>>u>>v;
a[u].push_back(v);
a[v].push_back(u);
}
for(int i=1;i<=k;i++)
{
cin>>u;
vc[u].push_back(i);
}
dfs(1,0);
for(int i=1;i<=k;i++)
for(int j=1;j<vc[i].size();j++)
collab(vc[i][0],vc[i][j]);
for(int i=1;i<=n;i++)
for(ll it:a[i])
if(getlab(i)!=getlab(it))
d[i]++;
for(int i=1;i<=n;i++)
if(d[i]==1)
ans++;
cout<<(ans+1)/2;
}
# | 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... |