제출 #559307

#제출 시각아이디문제언어결과실행 시간메모리
559307RedhoodPastiri (COI20_pastiri)C++14
49 / 100
1072 ms123544 KiB
#include<bits/stdc++.h>

#define fi first
#define se second
#define sz(x) (int)(x).size()
#define pb push_back
#define mkp make_pair
using namespace std;

typedef long long ll;
typedef long double ld;
//#define int long long
const int N = (int)5e5 + 10;
const int inf = 1e9;
vector < int > g[N];

int mnd[N];
int shrt[N], pred[N], h[N];

struct kek{
    int ans;
    int high;
    kek(){
        ans = 0;
        high = 1e9;
    }
};

kek state[N][2];

bool done[N][2];
void dfs(int v, int p, int H){
    h[v] = H;
    pred[v] = p;
    mnd[v] = (shrt[v] == 0 ? 0 : 1e9);
    for(auto &u : g[v]){
        if(u != p){
            dfs(u , v, H + 1);
            mnd[v] = min(mnd[v] , mnd[u] + 1);
        }
    }
}
int did[N][2];
bool bst[N];
bool better(kek &a , kek &b){
    if(a.ans == b.ans){
        return a.high < b.high;
    }
    return a.ans < b.ans;
}
void dfs1(int v){
    /// mnd[v];
    for(auto &u : g[v]){
        if(u != pred[v]){
            dfs1(u);
            if(better(state[u][1] , state[u][0]))
                bst[u] = 1;
            else
                bst[u] = 0;
        }
    }



    vector < int > small;
    for(auto &u : g[v]){
        if(u == pred[v])
            continue;
        if(mnd[u] + 1 > mnd[v]){
        }else{
            small.pb(u);
        }
    }

    for(int fl = 0;fl < 2; ++fl){
        for(auto &u : g[v]){
            if(u == pred[v])
                continue;
            if(mnd[u] + 1 > mnd[v]){
                state[v][fl].ans += state[u][1].ans;
                state[v][fl].high = min(state[v][fl].high, state[u][1].high);
            }
        }
         if(fl == 0){
                for(auto &u : small){
                    state[v][fl].ans += state[u][bst[u]].ans;
                    state[v][fl].high = min(state[v][fl].high, state[u][bst[u]].high);
                }
            }else{
                /// two options
                kek now = state[v][fl];
                for(auto &u : small){
                    now.ans += state[u][1].ans;
                    now.high = min(now.high, state[u][1].high);
                }
                /// another option is to cover by the current

                for(auto &u : small){
                    state[v][1].ans += state[u][bst[u]].ans;
                    state[v][1].high = min(state[v][1].high, state[u][bst[u]].high);
                }
                int x = h[v] - state[v][fl].high;

                bool put = 0;
                if(x != mnd[v]){
                    if(shrt[v] == mnd[v]){
                        state[v][fl].ans++, put = 1;
                        state[v][fl].high = min(state[v][fl].high, h[v] - shrt[v]);
                    }else
                        state[v][fl].ans = inf;
                }


        //        cerr << " lol " << v << ' ' << now.ans << ' ' << now.high << endl;

                if(better(state[v][fl], now)
                || (shrt[v]==0 && (now.high != h[v])) ){
                    did[v][fl] = 1 + put;

                }else{
                    state[v][fl] = now;
                }
            }
    }




}
bool visited[N][2];
bool ans[N];
void get_ans(int v , int fl){

    if(fl == 0){
        vector < int > small;
        for(auto &u : g[v]){
            if(u == pred[v])
                continue;
            if(mnd[u] + 1 > mnd[v]){
                get_ans(u, 1);
            }else{
                get_ans(u , bst[u]);
            }
        }
    }else{
        if(did[v][fl] > 0){
            ans[v] = did[v][fl] - 1;
            for(auto &u : g[v]){
                if(u == pred[v])
                    continue;
                if(mnd[u] + 1 > mnd[v]){
                    get_ans(u, 1);
                }else{
                    get_ans(u , bst[u]);
                }
            }
        }else{
//            assert(shrt[v] != 0);
            for(auto &u : g[v]){
                if(u == pred[v])
                    continue;
                get_ans(u , 1);
            }
        }

    }
}
signed main(){
    ios_base::sync_with_stdio(0), cin.tie(0) , cout.tie(0);
    int n , k;
    cin >> n >> k;
    for(int i = 0; i < n - 1; ++i){
        int a , b;
        cin >> a >> b;
        --a, --b;
        g[a].pb(b);
        g[b].pb(a);
    }
    vector < int > o(k);
    for(auto &i : o)
        cin >> i, --i;
    queue < int > bfs;
    for(auto &u : o)
        bfs.push(u);

    fill(shrt , shrt + N , -1);

    for(auto &u : o)
        shrt[u] = 0;
    while(!bfs.empty()){
        int v = bfs.front();
        bfs.pop();
        for(auto &u : g[v]){
            if(shrt[u] == -1){
                shrt[u] = shrt[v] + 1;
                bfs.push(u);
            }
        }
    }

    dfs(0 , -1, 0);




    dfs1(0);

    get_ans(0 , 1);


//    cout << "fukk \n";

//    for(int i = 0; i < n; ++i){
//        if(done[i][0])
//        cout << i << ' ' << 0 << ' ' << state[i][0].ans << '\n';
//
//        if(done[i][1])
//        cout << i << ' ' << 1 << ' ' << state[i][1].ans << '\n';
//        cout << " NEW \n";
//
//    }


    vector < int > take;
    for(int i = 0; i < n; ++i){
        if(ans[i])
            take.pb(i);
    }
    assert(sz(take) == state[0][1].ans);

    cout << state[0][1].ans << endl;
    for(auto &u : take)
        cout << u + 1 << ' ';
    cout << endl;




    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...