impl Solution {
    pub fn maximize_sweetness(sweetness: Vec<i32>, k: i32) -> i32 {
        let mut l = sweetness.clone().into_iter().fold(None, |min, x| match min {
            None => Some(x),
            Some(y) => Some(if x < y { x } else { y }),
        }).unwrap();
        let mut r = sweetness.clone().iter().fold(0, |mut r, &val| {r += val; r});
        while l < r {
            let (mid, mut sum, mut cut) = ((l + r + 1) / 2, 0, 0);
            for val in sweetness.clone() {
                sum += val;
                if sum >= mid {
                    sum = 0; cut += 1;
                    if cut > k {
                        break;
                    }
                }
            }
            if cut > k {
                l = mid;
            } else {
                r = mid - 1;
            }
        }

        return l;
    }
}

impl Solution {
    pub fn remove_subfolders(folder: Vec<String>) -> Vec<String> {
        let (mut f, mut ans) = (folder, vec![]);
        if f.is_empty() {
            return vec![];
        }
        f.sort();
        ans.push(f[0].clone());
        
        for i in 1..f.len() {
            let mut prefix = ans.last().unwrap().clone();
            prefix.push('/');
            let cur = f[i].clone();
            if cur.len() < prefix.len() || cur[..prefix.len()].to_string() != prefix  {
                ans.push(cur);
            }
        }
        return ans;
    }
}

use std::collections::HashMap;
use std::cmp;

impl Solution {
    fn dfs(g: &HashMap<i32, Vec<i32>>, ans: &mut i32, cur: i32, parent: i32) -> i32 {
        let val = g.get(&cur).unwrap();
        if val.len() == 1 && val[0] == parent {
            return 1;
        }

        let (mut a, mut b) = (0, 0);
        for item in val {
            if *item == parent {
                continue;
            }
            let next = Self::dfs(g, ans, *item, cur);
            if next > a {
                b = a;
                a = next;
            } else if next > b {
                b = next;
            }
            *ans = cmp::max(*ans, a + b);
        }
        return a + 1;
    }

    pub fn tree_diameter(edges: Vec<Vec<i32>>) -> i32 {
        let (mut tree, mut ans) : (HashMap<i32, Vec<i32>>, i32) = (HashMap::new(), 0);
        for edge in &edges {
            let (k, v) = (edge[0], edge[1]);
            tree.entry(k).or_insert(vec![]);
            tree.entry(v).or_insert(vec![]);
            tree.get_mut(&k).unwrap().push(v);
            tree.get_mut(&v).unwrap().push(k);
        }
        Self::dfs(&tree, &mut ans, edges[0][0], -1);
        return ans;
    }
}