#1078263 (Rust) No.3113 The farthest point

• 問題: No.3113 The farthest point
• ユーザー: かえる☔
• 提出日時: 2025-04-20 16:22:08
• 言語: Rust (1.83.0 + proconio)
• 結果: AC
• 実行時間: 184 ms / 2,000 ms
• コード長: 6,589 bytes
• コンパイル時間: 13,413 ms
• コンパイル使用メモリ: 402,292 KB
• 実行使用メモリ: 39,380 KB
• 最終ジャッジ日時: 2025-04-20 16:22:27
• 合計ジャッジ時間: 15,419 ms
• ジャッジサーバーID （参考情報）: judge4 / judge5

ファイルパターン	結果
sample	AC * 3
other	AC * 33

ソースコード

#![allow(unused_imports, non_snake_case, dead_code, unused_macros)]
use proconio::{input, marker::Usize1 as usize1, marker::Chars as chars};
use std::{collections::{BTreeMap, BTreeSet, HashMap, HashSet, VecDeque as Deque}, default::Default, io::Write, mem::swap};

macro_rules! chmax {
    ($target:expr, $value:expr) => {
        if $target < $value {
            $target = $value;
            true
        } else {false}
    };
}
macro_rules! chmin {
    ($target:expr, $value:expr) => {
        if $target > $value {
            $target = $value;
            true
        } else {false}
    };
}

fn yn(x: bool) {
    if x {
        println!("Yes")
    } else {
        println!("No")
    }
}

fn extend_euclid(a: i64, b: i64) -> Result<(i64, i64), i64> {
    /*
    ax+by=1 を満たすOk((x, y))を返す。存在しなければErr(gcd(a, b))を返す。
     */
    fn inner(a: i64, b: i64, ae: (i64, i64), be: (i64, i64)) -> Result<(i64, i64), i64> {
        if b == 0 {
            if a == 1 {
                return Ok(ae);
            } else {
                return Err(a);
            }
        }
        let mut new_be = (0, 0);
        new_be.0 = ae.0 - a / b * be.0;
        new_be.1 = ae.1 - a / b * be.1;
        inner(b, a%b, be, new_be)
    }
    inner(a, b, (1, 0), (0, 1))
}


#[derive(Debug)]
struct DisjointSetUnion {
    parents: Vec<usize>,
    children: Vec<Vec<usize>>,
    sizes: Vec<usize>,
}
impl DisjointSetUnion {
    fn new(N: usize) -> Self {
        let parents = (0..N).collect();
        let children = vec![vec![]; N];
        let sizes = vec![1; N];
        Self { parents, children, sizes }
    }
    fn root(&self, x: usize) -> usize {
        if self.parents[x] == x {
            x
        } else {
            self.root(self.parents[x])
        }
    }
    fn size(&self, x: usize) -> usize {
        self.sizes[self.root(x)]
    }
    fn union(&mut self, a: usize, b: usize) -> bool {
        let (a, b) = (self.root(a), self.root(b));
        if a==b {
            return false;
        }
        if self.size(a) > self.size(b) {
            self.parents[b] = a;
            self.children[a].push(b);
            self.sizes[a] += self.sizes[b];
            self.sizes[b] = 0;
        } else {
            self.parents[a] = b;
            self.children[b].push(a);
            self.sizes[b] += self.sizes[a];
            self.sizes[a] = 0;
        }
        true
    }
    fn connections(&self) -> Vec<usize> {
        let mut res = Vec::new();
        for i in 0..self.parents.len() {
            if self.root(i) == i {
                res.push(i)
            }
        }
        res
    }
}

struct SegTree<T: Copy> {
    size: usize,
    dat: Vec<T>,
    update_func: Box<dyn Fn(T, T) -> T>,
    identity: T,
}
impl<T: Copy> SegTree<T> {
    fn new(size: usize, update_func: impl Fn(T, T) -> T + 'static, identity: T) -> Self {
        let size = size.next_power_of_two();
        let dat = vec![identity.clone(); size*2-1];
        Self {
            size, dat, update_func: Box::new(update_func), identity,
        }
    }
    fn update(&mut self, mut i: usize, x: T) {
        i += self.size-1;
        self.dat[i] = x;
        while i > 0 {
            i = (i-1)/2;
            self.dat[i] = (self.update_func)(self.dat[i*2+1], self.dat[i*2+2]);
        }
    }
    fn query(&self, a: usize, b: usize) -> T {
        self.query_sub(a, b, 0, 0, self.size)
    }
    fn query_sub(&self, a: usize, b: usize, k: usize, l: usize, r: usize) -> T {
        if r <= a || b <= l {
            self.identity
        } else if a <= l && r <= b {
            self.dat[k]
        } else {
            (self.update_func)(self.query_sub(a, b, k*2+1, l, (l+r)/2), self.query_sub(a, b, k*2+2, (l+r)/2, r))
        }
    }
}
impl SegTree<i64> {
    fn new_rminq(size: usize) -> Self {
        Self::new(size, i64::min, std::i64::MAX)
    }
    fn new_rmaxq(size: usize) -> Self {
        Self::new(size, i64::max, std::i64::MIN)
    }
    fn new_rsq(size: usize) -> Self {
        Self::new(size, |a, b| a+b, 0)
    }
}
impl SegTree<usize> {
    fn new_rminq(size: usize) -> Self {
        Self::new(size, usize::min, std::usize::MAX)
    }
    fn new_rmaxq(size: usize) -> Self {
        Self::new(size, usize::max, std::usize::MIN)
    }
    fn new_rsq(size: usize) -> Self {
        Self::new(size, |a, b| a+b, 0)
    }
}


fn around(i: usize, j: usize, H: usize, W: usize) -> Vec<(usize, usize)> {
    let mut res = vec![];

    if i!=0 {
        res.push((i-1, j));
    }
    if j!=0 {
        res.push((i, j-1));
    }
    if i!=H-1 {
        res.push((i+1, j));
    }
    if j!=W-1 {
        res.push((i, j+1))
    }
    res
}
fn to_index(i: usize, j: usize, W: usize) -> usize {
    i*W+j
}



fn lowerchar2code(c: char) -> usize {
    c as usize - 'a' as usize
}



type ModType = usize;
static MOD: ModType = 998244353;

fn pow(base: ModType, power: ModType) -> ModType {
    if power == 0 {
        1
    } else if power == 1 {
        base % MOD
    } else {
        if power % 2 == 0 {
           pow(base, power/2).pow(2) % MOD
       } else {
           let tmp = pow(base, power/2).pow(2) % MOD;
           tmp * base % MOD
       }
    }
}

fn recip(x: ModType) -> ModType {
    pow(x, MOD-2)
}


fn main() {
    input! {
        N: usize,
        uvw: [(usize1, usize1, i64); N-1],
    }

    let mut children = vec![vec![]; N];
    let mut edges = vec![vec![]; N];
    for (u, v, w) in uvw {
        edges[u].push((v, w));
        edges[v].push((u, w));
    }

    let mut stack = vec![0];
    let mut reached = vec![false; N];
    reached[0] = true;

    while let Some(v) = stack.pop() {
        // println!("stack:{} {:?}", v, stack);
        for (u, w) in edges[v].clone() {
            if reached[u] {
                continue;
            }
            reached[u] = true;
            children[v].push((u, w));
            stack.push(u);
        }
    }
    // println!("{:?}", edges);
    //println!("{:?}", children);

    let mut solver = Solver{children, ans:0};
    solver.solve(0);
    println!("{}", solver.ans);

}

struct Solver {
    children: Vec<Vec<(usize, i64)>>,
    ans: i64,
}

impl Solver {
    fn solve(&mut self, v: usize) -> i64 {
        let mut children_ans = vec![];

        for (u, w) in self.children[v].clone() {
            children_ans.push(w+self.solve(u));
        }

        children_ans.extend([0, 0]);
        children_ans.sort(); children_ans.reverse();
        // println!("{} {:?}", v, children_ans);
        chmax!(self.ans, children_ans[0] + children_ans[1]);
        children_ans[0]
    }
}