#include <bits/stdc++.h>
using namespace std;
#define ll int
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... |