提出 #57058599

---

ソースコード 拡げる

use proconio::{input, marker::Usize1};

fn main() {
    input! {
        n: usize,
        k: usize,
        ab: [(Usize1, Usize1); n - 1],
        v: [Usize1; k],
    }

    let r = v[0];
    let g = {
        let mut g = vec![vec![]; n];
        for &(a, b) in &ab {
            g[a].push(b);
            g[b].push(a);
        }
        g
    };

    let par = par(&g, r);
    let mut used = vec![false; n];
    for &v in &v {
        for u in std::iter::successors(Some(v), |&v| (v < n).then(|| par[v]))
            .take_while(|&u| u < n)
        {
            if used[u] {
                break;
            }
            used[u] = true;
        }
    }
    let res = used.iter().filter(|&&u| u).count();
    println!("{res}");
}

fn par(g: &[Vec<usize>], r: usize) -> Vec<usize> {
    fn dfs(g: &[Vec<usize>], v: usize, pv: usize, par: &mut [usize]) {
        for &nv in g[v].iter().filter(|&&nv| nv != pv) {
            par[nv] = v;
            dfs(g, nv, v, par);
        }
    }
    let n = g.len();
    let mut res = vec![n; n];
    dfs(g, r, n, &mut res);
    res
}

提出情報

ジャッジ結果