Submission #1365452

#TimeUsernameProblemLanguageResultExecution timeMemory
1365452ChocoPastiri (COI20_pastiri)C++20
0 / 100
144 ms62396 KiB
#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize("O3")
#define ll  long long 
#define fori(i,j,k) for(ll i=j; i<=k;i++)
#define study ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#define pb push_back
#define all(s) s.begin(),s.end()
#define ins insert
#define ss second
#define ff first
#ifndef DB
#define DB 0
#endif 
#define debugl(l) if constexpr((l)<DB)
#define debug debugl(0)
const ll sz=2e5+10;
ll INF=1e12;
ll mod=1e9+7;
ll limit=1;
vector<vector<ll>>gr,s;
vector<ll>dist;
void restart(ll n,ll k){
    gr.resize(n+10);
    s.resize(n+10);
    dist.assign(n+10,INF);
}
void work(){
    ll n,k;
    cin>>n>>k;
    restart(n,k);
    vector<ll>check(n+10,-1);
    fori(i,1,n-1){
        ll a,b;
        cin>>a>>b;
        gr[a].pb(b);
        gr[b].pb(a);
    }
    queue<pair<ll,ll>>q;
    fori(i,1,k){
        ll nod;
        cin>>nod;
        q.push({0,nod});
        dist[nod]=0;
        s[nod].pb(nod);
        check[nod]++;
    }
    while(!q.empty()){
        ll nod=q.front().ss;
        ll dit=q.front().ff;
        q.pop();
        if(dit!=dist[nod])
        continue;
        for(auto x: gr[nod]){
            if((dit+1)<dist[x]){
                dist[x]=dit+1;
                s[x]=s[nod];
            }
            else if((dit+1)==dist[x]){
                for(auto y: s[nod])
                s[x].pb(y);
            }
        }
    }
    vector<pair<ll,ll>>yes;
    fori(i,1,n){
        yes.pb({s[i].size(),i});
    }
    vector<ll>ans(n+10,0);
    ll cur=0;
    sort(all(yes)); reverse(all(yes));
    for(auto x: yes){
        bool ok=1;
        ll nod=x.ss;
        for(auto y: s[nod]){
            if(check[y]==0)
            ok=0;
        }
        if(ok==1)
        continue;
        for(auto y: s[nod]){
            check[y]++;
        }
        ans[nod]=1;
        cur++;
    }
    for(auto x: yes){
        ll nod=x.ss;
        if(!ans[nod])
        continue;
        bool ok=0;
        for(auto y: s[nod]){
            if(check[y]>1)
            ok=1;
        }
        if(ok) continue;
        for(auto y: s[nod]){
            check[y]--;
        }
        ans[nod]=0;
        cur--;
    }
    cout<<cur<<endl;
    fori(i,1,n){
        if(ans[i])
        cout<<i<<" ";
    }
}
int main()
{
    // #ifndef LOCAL
    // freopen("snowcow.in","r",stdin);
    // freopen("snowcow.out","w",stdout);
    // #endif
    study;
    ll t=1;
    //cin>>t;
    fori(i,1,t){
    work();
    }
}
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...