Non-Decreasing Colorful Path の解説

dp[v] := vを根とする部分木での頂点数最大値

ufで同じ値を消す。

fn dfs(v: usize, to: &Vec<Vec<usize>>, dp: &mut Vec<isize>, g: usize) -> isize {
    if dp[v] != -2 {
        return dp[v];
    }
    if v == g {
        return 1;
    }
    let mut best = -1;
    for &v2 in to[v].iter() {
        let pre = dfs(v2, to, dp, g);
        if pre == -1 {
            continue;
        }
        best = max(best, pre + 1);
    }
    dp[v] = best;
    best
}

fn main() {
    input! {
        n: usize,
        m: usize,
        a: [usize; n],
        uv: [(Usize1, Usize1); m]
    }
    let mut uf = Dsu::new(n);
    let mut to = vec![vec![]; n];
    for &(u, v) in uv.iter() {
        if a[u] == a[v] {
            uf.merge(u, v);
        }
    }
    for &(u, v) in uv.iter() {
        if uf.same(u, v) {
            continue;
        }
        let u = uf.leader(u);
        let v = uf.leader(v);
        assert!(a[u] != a[v]);
        if a[u] > a[v] {
            to[v].push(u);
        } else {
            to[u].push(v);
        }
    }
    let mut dp = vec![-2; n];
    let ans = dfs(uf.leader(0), &to, &mut dp, uf.leader(n - 1));
    if ans == -1 {
        return println!("0");
    }
    println!("{}", ans);
}