Cod sursa(job #3371656)

Utilizator IeremiaNicolaescu Ieremia Ieremia Data 31 octombrie 2026 11:24:27
Problema Componente biconexe Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.58 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>

using namespace std;

ifstream fin("freakadebunic.in");
ofstream fout("freakadebunic.out");

const int NMAX = 100005;

vector<int> g[NMAX];
int parent_node[NMAX], depth[NMAX], heavy[NMAX], head_hld[NMAX], tin[NMAX];
int trupe[NMAX];
bool is_ans[NMAX];
int timer;

// Pasul 1: Aflăm adâncimile, părinții și cel mai "greu" fiu (cu cel mai mare subarbore)
int dfs1(int u, int p) {
    int sz = 1, max_c_sz = 0;
    parent_node[u] = p;
    depth[u] = depth[p] + 1;
    heavy[u] = 0;

    for (int v : g[u]) {
        if (v != p) {
            int c_sz = dfs1(v, u);
            sz += c_sz;
            if (c_sz > max_c_sz) {
                max_c_sz = c_sz;
                heavy[u] = v;
            }
        }
    }
    return sz;
}

// Pasul 2: Numerotăm timpii de intrare (tin) și construim lanțurile HLD
void dfs2(int u, int p, int h) {
    head_hld[u] = h;
    tin[u] = ++timer;

    if (heavy[u]) {
        dfs2(heavy[u], u, h);
    }

    for (int v : g[u]) {
        if (v != p && v != heavy[u]) {
            dfs2(v, u, v);
        }
    }
}

// Pasul 3: Funcție rapidă pentru calculul LCA cu HLD
int get_lca(int u, int v) {
    while (head_hld[u] != head_hld[v]) {
        if (depth[head_hld[u]] > depth[head_hld[v]]) {
            u = parent_node[head_hld[u]];
        } else {
            v = parent_node[head_hld[v]];
        }
    }
    return depth[u] < depth[v] ? u : v;
}

// Criteriu de sortare a trupelor după ordinea DFS
bool cmp(int a, int b) {
    return tin[a] < tin[b];
}

int main() {
    int n, k;
    if (!(fin >> n >> k)) return 0;

    for (int i = 1; i <= k; i++) {
        fin >> trupe[i];
    }

    for (int i = 1; i < n; i++) {
        int u, v;
        fin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }

    // Precalculare pe arbore
    dfs1(1, 0);
    dfs2(1, 0, 1);

    // Sortăm nodurile cu trupe după timpul de intrare tin
    sort(trupe + 1, trupe + k + 1, cmp);

    // Calculăm LCA doar pentru nodurile vecine din vectorul sortat
    int cnt = 0;
    for (int i = 1; i < k; i++) {
        int lca = get_lca(trupe[i], trupe[i + 1]);
        if (!is_ans[lca]) {
            is_ans[lca] = true;
            cnt++;
        }
    }

    // Afișăm numărul de noduri "devreme" și nodurile în ordine crescătoare
    fout << cnt << "\n";
    for (int i = 1; i <= n; i++) {
        if (is_ans[i]) {
            fout << i << " ";
        }
    }
    fout << "\n";

    return 0;
}