#include<bits/stdc++.h>
#define fi first
#define se second
#define rep(a, b) for(int a = 0; a < (b); a++)
using namespace std;
typedef long long ll;
typedef vector<ll> vi;
typedef vector<ll> vl;
const int N=2e5+10;
const int L=19;
const int M=4e6+10;
vi graf[N],graf2[M],r[N],graf3[M];
int t[N],gl[N],spojna[M],ile[M],pre[N],post[M];
pair<int,int> jump[N][L+1];
int l=0,l2=0,n,k;
bitset<M>kan;
bitset<M>vis;
void add(int a,int b){
graf2[a].push_back(b),graf3[b].push_back(a);
}
void dfs(int v,int o,int g){
pre[v]=++l2;
gl[v]=g;
jump[v][0]={o,++l};
add(l,t[o-1]);
for(int j=1;j<=L;j++) jump[v][j].fi=jump[jump[v][j-1].fi][j-1].fi,jump[v][j].se=++l,add(l,jump[v][j-1].se),add(l,jump[jump[v][j-1].fi][j-1].se);
for(auto u:graf[v]){
if(u==o) continue;
dfs(u,v,g+1);
}
}
int lca(int a,int b){
if(gl[a]<gl[b]) swap(a,b);
for(int i=L;i>=0;i--) if(gl[jump[a][i].fi]>=gl[b]) a=jump[a][i].fi;
if(a==b) return a;
int res=0;
for(int i=L;i>=0;i--){
if(jump[a][i].fi==jump[b][i].fi) res=jump[a][i].fi;
else a=jump[a][i].fi,b=jump[b][i].fi;
}
return res;
}
void dod(int a,int l,int x){
for(int i=L;i>=0;i--) if(gl[jump[a][i].fi]>=gl[l]) add(x,jump[a][i].se),a=jump[a][i].fi;
}
void dfs2(int v){
if(vis[v]) return;
vis[v]=1;
for(auto u:graf2[v]) dfs2(u);
post[l2++]=v;
}
void dfs3(int v,int& s,bool& b){
if(vis[v]) return;
vis[v]=1;
spojna[v]=s;
if(v<=k-1){
if(!b) b=1,s++;
ile[s]++;
}
for(auto u:graf3[v]) dfs3(u,s,b);
}
void solve(){
cin>>n>>k;
rep(i,n-1){
int a,b;
cin>>a>>b;
graf[a].push_back(b),graf[b].push_back(a);
}
l=k-1;
rep(i,n){
cin>>t[i];
t[i]--;
r[t[i]].push_back(i+1);
}
dfs(1,1,1);
vector<pair<int,int> >vv;
rep(i,k){
vv.clear();
for(auto u:r[i]) vv.push_back({pre[u],u});
sort(vv.begin(),vv.end());
for(int j=1;j<vv.size();j++){
int l=lca(vv[j].se,vv[j-1].se);
dod(vv[j].se,l,i),dod(vv[j-1].se,l,i);
}
}
l2=0;
rep(i,l+1) dfs2(i);
rep(i,l+1) vis[i]=0;
int curr=0;
bool xd=0;
for(int i=l;i>=0;i--) if(!vis[post[i]]) dfs3(post[i],++curr,xd),xd=0;
rep(i,l+1){
bool b=0;
for(auto u:graf2[i]) if(spojna[i]!=spojna[u]) b=1;
if(!kan[spojna[i]]) kan[spojna[i]]=b;
}
int res=INT_MAX;
rep(i,k) if(!kan[spojna[i]]) res=min(res,ile[spojna[i]]);
cout<<res-1<<"\n";
}
int main(){
ios_base::sync_with_stdio(0),cin.tie(0);
solve();
}
Compilation message
capital_city.cpp: In function 'void solve()':
capital_city.cpp:81:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
81 | for(int j=1;j<vv.size();j++){
| ~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
87 ms |
197572 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
87 ms |
197572 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1570 ms |
524288 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
87 ms |
197572 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
