Laskettelukeskus

use std::{cmp, io};

#[derive(Clone, Debug)]
struct Slope {
    plow_count: u64,
    children: Vec<usize>,
}

fn main() {
    let mut input = String::new();
    io::stdin().read_line(&mut input).unwrap();
    let n: usize = input.trim().parse().unwrap();

    let mut slopes = vec![
        Slope {
            plow_count: 0,
            children: Vec::new(),
        };
        n
    ];

    build_graph(&mut slopes, n);
    read_plow_counts(&mut slopes);

    let result = count_paths(&slopes, 0);
    println!("{}", result);
}

fn build_graph(slopes: &mut Vec<Slope>, n: usize) {
    for _ in 0..n - 1 {
        let mut input = String::new();
        io::stdin().read_line(&mut input).unwrap();
        let nums: Vec<usize> = input
            .split_whitespace()
            .map(|s| s.parse().unwrap())
            .collect();
        let parent = nums[0] - 1;
        let child = nums[1] - 1;
        slopes[parent].children.push(child);
    }
}
fn read_plow_counts(slopes: &mut Vec<Slope>) {
    let mut input = String::new();
    io::stdin().read_line(&mut input).unwrap();
    let nums: Vec<u64> = input
        .split_whitespace()
        .map(|s| s.parse().unwrap())
        .collect();
    for (i, num) in nums.iter().enumerate() {
        slopes[i].plow_count = *num;
    }
}

fn count_paths(slopes: &Vec<Slope>, index: usize) -> u64 {
    let slope = &slopes[index];
    if slope.children.is_empty() {
        slope.plow_count
    } else {
        cmp::max(
            slope.plow_count,
            slope
                .children
                .iter()
                .map(|&i| count_paths(&slopes, i))
                .sum(),
        )
    }
}

Test 1

Group: 1, 2

Verdict: ACCEPTED

Test 2

Group: 1, 2

Verdict: ACCEPTED

Test 3

Group: 1, 2

Verdict: ACCEPTED

Test 4

Group: 2

Verdict: ACCEPTED

Test 5

Group: 2

Verdict: ACCEPTED

Test 6

Group: 1, 2

Verdict: ACCEPTED

Test 7

Group: 2

Verdict: ACCEPTED

Test 8

Group: 1, 2

Verdict: ACCEPTED

Test 9

Group: 2

Verdict: ACCEPTED

Test 10

Group: 1, 2

Verdict: ACCEPTED

Test 11

Group: 2

Verdict: ACCEPTED

Test 12

Group: 1, 2

Verdict: ACCEPTED

Test 13

Group: 2

Verdict: ACCEPTED