Submission #1111377

---

Source Code Expand

use std::io::{self, Stdin};
use std::str::{self, FromStr};
use std::error::Error;
use std::thread;
use std::cmp::*;
fn exec() {
    let mut sc = Scanner::new();
    let n: usize = sc.ne();
    let mut adj = vec![Vec::new(); n];
    for _ in 0..n - 1 {
        let u = sc.ne::<usize>() - 1;
        let v = sc.ne::<usize>() - 1;
        adj[u].push(v);
        adj[v].push(u);
    }
    fn dfs(cur: usize,
           par: usize,
           adj: &Vec<Vec<usize>>,
           d: i64,
           mut vis: &mut Vec<usize>,
           mut depth: &mut Vec<i64>) {
        vis.push(cur);
        depth.push(d);
        for &nxt in &adj[cur] {
            if nxt == par {
                continue;
            }
            dfs(nxt, cur, &adj, d + 1, &mut vis, &mut depth);
            vis.push(cur);
            depth.push(d);
        }
    }
    let mut vis = Vec::new();
    let mut depth = Vec::new();
    let _ = dfs(0, 0, &adj, 0, &mut vis, &mut depth);
    let mut id = vec![1000000000; n];
    for i in 0..vis.len() {
        id[vis[i]] = min(id[vis[i]], i);
    }
    let mut seg = SegTree::fromseq(&depth);
    let q: usize = sc.ne();
    for _ in 0..q {
        let u = sc.ne::<usize>() - 1;
        let v = sc.ne::<usize>() - 1;
        let d = seg.query(min(id[u], id[v]), max(id[u], id[v]) + 1);
        print!("{}\n", depth[id[u]] + depth[id[v]] - d * 2 + 1);
    }
}
#[allow(dead_code)]
struct SegTree<T> {
    n: usize,
    data: Vec<T>,
}

// 根ノードを1とする
#[allow(dead_code)]
impl<T: Monoid<T>> SegTree<T> {
    fn new(n_: usize) -> SegTree<T> {
        let mut res_n = 1;
        while res_n < n_ {
            res_n <<= 1;
        }
        SegTree::<T> {
            n: res_n,
            data: vec![T::ide(); 2 * res_n],
        }
    }
    fn fromseq(seq: &Vec<T>) -> SegTree<T> {
        let n_ = seq.len();
        let mut res_seg = SegTree::<T>::new(n_);
        for i in 0..n_ {
            res_seg.data[i + res_seg.n] = seq[i];
        }
        for i in (1..res_seg.n).rev() {
            res_seg.data[i] = T::merge(res_seg.data[2 * i], res_seg.data[2 * i + 1])
        }
        res_seg
    }
    fn update(&mut self, k_: usize, x: T) {
        let mut k = k_ + self.n;
        self.data[k] = x;
        while k > 0 {
            k = (k - 1) >> 1;
            self.data[k] = T::merge(self.data[k * 2], self.data[k * 2 + 1]);
        }
    }
    fn query(&mut self, ql: usize, qr: usize) -> T {
        let n_ = self.n;
        self.__query(ql, qr, 1, 0, n_)
    }
    fn __query(&mut self, ql: usize, qr: usize, k: usize, nl: usize, nr: usize) -> T {
        if nr <= ql || qr <= nl {
            return T::ide();
        };
        if ql <= nl && nr <= qr {
            return self.data[k];
        };
        let mid = (nl + nr) / 2;
        let vl = self.__query(ql, qr, k * 2, nl, mid);
        let vr = self.__query(ql, qr, k * 2 + 1, mid, nr);
        T::merge(vl, vr)
    }
}


trait Monoid<T>: Copy + Clone {
    fn merge(T, T) -> T;
    fn ide() -> T;
}

// Range Minimum Query
type Int = i64;
impl Monoid<Int> for Int {
    fn merge(l: Int, r: Int) -> Int {
        std::cmp::min(l, r)
    }
    fn ide() -> Int {
        std::i32::MAX as Int
    }
}

fn main() {
    const DEFAULT_STACK: usize = 16 * 1024 * 1024;
    let builder = thread::Builder::new();
    let th = builder.stack_size(DEFAULT_STACK);
    let handle = th.spawn(|| { exec(); }).unwrap();
    let _ = handle.join();
}

#[allow(dead_code)]
struct Scanner {
    stdin: Stdin,
    id: usize,
    buf: Vec<u8>,
}

#[allow(dead_code)]
impl Scanner {
    fn new() -> Scanner {
        Scanner {
            stdin: io::stdin(),
            id: 0,
            buf: Vec::new(),
        }
    }
    fn next_line(&mut self) -> Option<String> {
        let mut res = String::new();
        match self.stdin.read_line(&mut res) {
            Ok(0) => return None,
            Ok(_) => Some(res),
            Err(why) => panic!("error in read_line: {}", why.description()),
        }
    }
    fn next<T: FromStr>(&mut self) -> Option<T> {
        while self.buf.len() == 0 {
            self.buf = match self.next_line() {
                Some(r) => {
                    self.id = 0;
                    r.trim().as_bytes().to_owned()
                }
                None => return None,
            };
        }
        let l = self.id;
        assert!(self.buf[l] != b' ');
        let n = self.buf.len();
        let mut r = l;
        while r < n && self.buf[r] != b' ' {
            r += 1;
        }
        let res = match str::from_utf8(&self.buf[l..r]).ok().unwrap().parse::<T>() {
            Ok(s) => Some(s),
            Err(_) => panic!("parse error"),
        };
        while r < n && self.buf[r] == b' ' {
            r += 1;
        }
        if r == n {
            self.buf.clear();
        } else {
            self.id = r;
        }
        res
    }
    fn ne<T: FromStr>(&mut self) -> T {
        self.next::<T>().unwrap()
    }
}

Submission Info

Judge Result