Company Queries II

warning: unused imports: `Reverse`, `max`, `min`
 --> input/code.rs:1:16
  |
1 | use std::cmp::{max, min, Reverse};
  |                ^^^  ^^^  ^^^^^^^
  |
  = note: `#[warn(unused_imports)]` on by default

warning: unused imports: `BTreeMap`, `BinaryHeap`, `HashMap`, `HashSet`
 --> input/code.rs:2:24
  |
2 | use std::collections::{BTreeMap, BinaryHeap, HashMap, HashSet};
  |                        ^^^^^^^^  ^^^^^^^^^^  ^^^^^^^  ^^^^^^^

warning: unused import: `std::process::exit`
 --> input/code.rs:4:5
  |
4 | use std::process::exit;
  |     ^^^^^^^^^^^^^^^^^^

warning: 3 warnings emitted

use std::cmp::{max, min, Reverse};
use std::collections::{BTreeMap, BinaryHeap, HashMap, HashSet};
use std::io::{self, Read};
use std::process::exit;

macro_rules! input {
    ($it: expr) => {
        $it.next().unwrap().parse().unwrap()
    };
    ($it: expr, $T: ty) => {
        $it.next().unwrap().parse::<$T>().unwrap()
    };
}
/*
mod classes;
mod homework;

fn main() {
    // println!("{}", "-".repeat(20));
    // classes::c15::task2();
    homework::hw6::task1();
    // println!("{}", "-".repeat(20));
}
// */

fn dfs(v: usize, p: usize, d: usize, c: &Vec<Vec<usize>>,
       depth: &mut Vec<usize>, up: &mut Vec<Vec<usize>>) {
    depth[v] = d;
    up[v][0] = p;
    for &child in &c[v] {
        dfs(child, v, d + 1, c, depth, up);
    }
}

fn main() {
    let mut buf = String::new();
    io::stdin().read_to_string(&mut buf).unwrap();

    let mut it = buf.split_whitespace();

    let (n, q): (usize, usize) = (input!(it), input!(it));

    if n == 1 {
        for _ in 0..q {
            let (_a, _b): (usize, usize) = (input!(it), input!(it));
            println!("1");
        }
        return;
    }

    let v: Vec<usize> = (0..n-1).map(|_| input!(it)).collect();
    let mut p = vec![0; n + 1];
    p[1] = 0;
    for i in 0..n - 1 {
        p[i + 2] = v[i];
    }

    let log = 20;

    let mut up = vec![vec![0; log]; n + 1];
    let mut depth = vec![0; n + 1];

    let mut c = vec![Vec::new(); n + 1];
    for i in 2..=n {
        c[p[i]].push(i);
    }

    dfs(1, 0, 0, &c, &mut depth, &mut up);

    for j in 1..log {
        for i in 1..=n {
            up[i][j] = up[up[i][j - 1]][j - 1];
        }
    }

    let lca = |mut a: usize, mut b: usize| -> usize {
        if depth[a] < depth[b] {
            std::mem::swap(&mut a, &mut b);
        }
        let mut remaining = depth[a] - depth[b];
        for j in 0..log {
            if remaining % 2 == 1 {
                a = up[a][j];
            }
            remaining /= 2;
        }
        if a == b {
            return a;
        }
        for j in (0..log).rev() {
            if up[a][j] != up[b][j] {
                a = up[a][j];
                b = up[b][j];
            }
        }
        up[a][0]
    };

    for _ in 0..q {
        let (a, b): (usize, usize) = (input!(it), input!(it));
        println!("{}", lca(a, b));
    }
}

Test 1

Verdict: ACCEPTED

Test 2

Verdict: ACCEPTED

Test 3

Verdict: ACCEPTED

Test 4

Verdict: ACCEPTED

Test 5

Verdict: ACCEPTED

Test 6

Verdict: ACCEPTED

Test 7

Verdict: ACCEPTED

Test 8

Verdict: ACCEPTED

Test 9

Verdict: ACCEPTED

Test 10

Verdict: ACCEPTED

Test 11

Verdict: ACCEPTED

Test 12

Verdict: ACCEPTED