Submission #59394583

---

Source Code Expand

use proconio::input;

pub fn main() {
    input! {
        n: usize,
        uv: [(usize, usize); n - 1],
    };

    let mut adj = vec![Vec::new(); n + 1];
    let mut degrees = vec![0; n + 1];

    for (u, v) in uv {
        adj[u].push(v);
        adj[v].push(u);
        degrees[u] += 1;
        degrees[v] += 1;
    }

    let mut visited = vec![false; n + 1];
    let mut total_pairs = 0u64;

    for node in 1..=n {
        if degrees[node] == 3 && !visited[node] {
            let mut stack = Vec::new();
            stack.push(node);
            visited[node] = true;

            let mut degree_3_nodes = Vec::new();
            degree_3_nodes.push(node);

            let mut degree_2_nodes = Vec::new();

            while let Some(u) = stack.pop() {
                for &v in &adj[u] {
                    if degrees[v] == 3 && !visited[v] {
                        visited[v] = true;
                        stack.push(v);
                        degree_3_nodes.push(v);
                    }
                }
            }

            for &u in &degree_3_nodes {
                for &v in &adj[u] {
                    if degrees[v] == 2 {
                        degree_2_nodes.push(v);
                    }
                }
            }

            let k = degree_2_nodes.len();
            if k >= 2 {
                total_pairs += (k * (k - 1) / 2) as u64;
            }
        }
    }

    println!("{}", total_pairs);
}

Submission Info

Judge Result