AtCoder Beginner Contest 447 F

https://atcoder.jp/contests/abc447/tasks/abc447_f

ノードごとの次数（直接つながっているノードの数）を調べます。そのとき次数が3以上から始まって、4以上が続いて、3以上で終わるパスを調べます。そのために、3以上のみでなるエッジで新しいグラフを作ります。そのとき4-3-4みたいなパスはダメなので、4-3, 3-4と次数3のノードは分割して端点にします。そうして、連結成分に分けて、各々の木の径を求めます。
しかし、よくよく問題文を読むと、1-2-1というグラフは長さ1のムカデグラフになりますね。そこだけ注意します。

// Centipede Graph
#![allow(non_snake_case)]


//////////////////// library ////////////////////

fn read<T: std::str::FromStr>() -> T {
    let mut line = String::new();
    std::io::stdin().read_line(&mut line).ok();
    line.trim().parse().ok().unwrap()
}

fn read_vec<T: std::str::FromStr>() -> Vec<T> {
    read::<String>().split_whitespace()
            .map(|e| e.parse().ok().unwrap()).collect()
}


//////////////////// UnionFind ////////////////////

use std::cmp::max;

type Node = usize;

struct UnionFind {
    parents: Vec<Node>,
    heights: Vec<i32>,
}

impl UnionFind {
    fn new(N: usize) -> UnionFind {
        let parents: Vec<Node> = (0..N).collect();
        let heights: Vec<i32> = vec![1; N];
        UnionFind { parents, heights }
    }
    
    fn is_root(&self, v: Node) -> bool {
        self.parents[v] == v
    }
    
    fn is_connected(&self, u: Node, v: Node) -> bool {
        self.root(u) == self.root(v)
    }
    
    fn connect(&mut self, u: Node, v: Node) {
        let r1 = self.root(u);
        let r2 = self.root(v);
        if r1 == r2 {
            return
        }
        
        let h1 = self.heights[r1];
        let h2 = self.heights[r2];
        if h1 <= h2 {   // r2にr1がぶら下がる
            self.parents[r1] = r2;
            self.heights[r2] = max(self.heights[r2], self.heights[r1]+1);
        }
        else {
            self.parents[r2] = r1;
            self.heights[r1] = max(self.heights[r1], self.heights[r2]+1);
        }
    }
    
    fn root(&self, v0: Node) -> Node {
        if self.is_root(v0) {
            v0
        }
        else {
            let p = self.parents[v0];
            self.root(p)
        }
    }
    
    fn divide_into_connected(&self) -> Vec<Vec<Node>> {
        let N = self.parents.len();
        let mut m: HashMap<Node, Vec<Node>> = HashMap::new();
        for v in 0..N {
            let r = self.root(v);
            let e = m.entry(r).or_insert(vec![]);
            (*e).push(v)
        }
        m.values().cloned().collect::<Vec<_>>()
    }
}


//////////////////// Graph ////////////////////

use std::collections::{VecDeque, HashMap};

type Edge = (Node, Node);

fn read_edge() -> Edge {
    let v: Vec<usize> = read_vec();
    let (U, V) = (v[0]-1, v[1]-1);
    (U, V)
}

struct Graph {
    g: Vec<Vec<Node>>
}

impl Graph {
    fn enumerate_edges(&self) -> Vec<Edge> {
        let mut edges: Vec<Edge> = vec![];
        for u in 0..self.g.len() {
            for &v in self.g[u].iter() {
                if u < v {
                    edges.push((u, v))
                }
            }
        }
        edges
    }
    
    fn divide_into_connected(&self) -> Vec<Graph> {
        let N = self.g.len();
        let mut uf = UnionFind::new(N);
        for (u, v) in self.enumerate_edges() {
            uf.connect(u, v)
        }
        
        let mut gs: Vec<Graph> = vec![];
        for vs in uf.divide_into_connected() {
            let L = vs.len();
            let m: HashMap<Node, Node> = vs.iter().cloned().zip(0..L).collect();
            let mut g: Vec<Vec<Node>> = vec![vec![]; L];
            for u in 0..vs.len() {
                g[u] = self.g[vs[u]].iter().map(|v| *m.get(v).unwrap()).
                                                    collect::<Vec<Node>>()
            }
            gs.push(Graph { g })
        }
        gs
    }
    
    fn find_farthest_point(&self, v0: Node) -> (Node, i32) {
        let N = self.g.len();
        let mut q: VecDeque<Node> = VecDeque::new();
        q.push_back(v0);
        let mut dists: Vec<i32> = vec![i32::MAX; N];
        dists[v0] = 0;
        while let Some(v) = q.pop_front() {
            let d = dists[v];
            for &v1 in self.g[v].iter() {
                if dists[v1] == i32::MAX {
                    dists[v1] = d + 1;
                    q.push_back(v1)
                }
            }
        }
        dists.into_iter().enumerate().max_by_key(|(_, d)| *d).unwrap()
    }
    
    fn diameter(&self) -> i32 {
        let (v1, _) = self.find_farthest_point(0);
        let (_, d2) = self.find_farthest_point(v1);
        d2
    }
    
    fn read() -> Graph {
        let N: usize = read();
        let mut g: Vec<Vec<Node>> = vec![vec![]; N];
        for _ in 0..N-1 {
            let (u, v) = read_edge();
            g[u].push(v);
            g[v].push(u)
        }
        Graph { g }
    }
}


//////////////////// process ////////////////////

fn divide_three_degree_nodes(graph: &Graph) -> Graph {
    let N = graph.g.len();
    let mut g: Vec<Vec<Node>> = vec![vec![]; N];
    for (u, v) in graph.enumerate_edges() {
        if graph.g[u].len() < 3 || graph.g[v].len() < 3 {
            continue
        }
        
        let mut u1 = u;
        if graph.g[u].len() == 3 && g[u].is_empty() {
            u1 = g.len();
            g.push(vec![])
        }
        let mut v1 = v;
        if graph.g[v].len() == 3 && g[v].is_empty() {
            v1 = g.len();
            g.push(vec![])
        }
        
        g[u1].push(v1);
        g[v1].push(u1)
    }
    
    Graph { g }
}

fn F_each(graph: Graph) -> i32 {
    if graph.g.iter().all(|vs| vs.len() < 3) {
        return if graph.g.len() <= 2 { 0 } else { 1 }
    }
    
    let new_graph = divide_three_degree_nodes(&graph);
    let graphs = new_graph.divide_into_connected();
    graphs.into_iter().map(|g| g.diameter() + 1).max().unwrap()
}

fn F(Q: usize) {
    for _ in 0..Q {
        let graph = Graph::read();
        println!("{}", F_each(graph))
    }
}

fn main() {
    let Q: usize = read();
    F(Q)
}