Laskettelukeskus

use std::cmp::max;
use std::collections::HashSet;
use std::io;

fn main() {
    let stdin = io::stdin();

    let slope_count = { // AKA n
        let mut input: String = String::new();
        stdin.read_line(&mut input).unwrap();
        input.replace("\r", "").replace("\n", "").parse::<usize>().unwrap()
    };


    let (mut slopes, mut bottom_slopes) = {
        // All slopes indexed by their IDs.
        let mut slopes: Vec<SkiSlope> = Vec::with_capacity(slope_count);
        // IDs of slopes with no route below. Initially, every slope.
        let mut bottom_slopes = HashSet::with_capacity(slope_count);

        for i in 0..slope_count {
            slopes.push(SkiSlope {
                upward_connections: HashSet::new(),
                plows: 0, // Will be initialized later.
                child_plows: 0 // Will be initialized later.
            });
            bottom_slopes.insert(i);
        }

        (slopes, bottom_slopes)
    };

    // Read routes
    {
        // Read line slope_count - 1 times
        for _ in 1..slope_count {
            let mut input: String = String::new();
            stdin.read_line(&mut input).unwrap();

            let route: Vec<usize> = input.replace("\r", "").replace("\n", "").split_whitespace().map(|value| {
                value.parse::<usize>().unwrap() - 1 // Indexes are given starting from 1, so they need to be decremented
            }).collect();

            // A route exists from route[0] to route[1].

            // route[0] continues downwards, and must be removed from bottom_slopes.
            bottom_slopes.remove(&route[0]);

            slopes[route[1]].upward_connections.insert(route[0]);
        }
    };

    // Read number of required plows.
    {
        let mut input: String = String::new();
        stdin.read_line(&mut input).unwrap();

        input
            .replace("\r", "")
            .replace("\n", "")
            .split_whitespace()
            .enumerate()
            .for_each(|(i, value)| {
                slopes[i].plows = value.parse::<u32>().unwrap()
            });
    }

    // Calculate required plows from bottom to top.
    while !&bottom_slopes.is_empty() {
        let mut next_slopes = HashSet::new();
        for bottom_slope_id in &bottom_slopes {
            let slope = &mut slopes[*bottom_slope_id];
            slope.plows = max(slope.plows, slope.child_plows);
            let plows = slope.plows;
            for upper_slope_id in slope.upward_connections.clone() {
                let mut upper_slope = &mut slopes[upper_slope_id];
                upper_slope.child_plows += plows;
                next_slopes.insert(upper_slope_id);
            }
        }
        bottom_slopes = next_slopes;
    }

    println!("{}", slopes[0].plows); // Print required plows for the root ski slope.
}

struct SkiSlope {
    upward_connections: HashSet<usize>,
    plows: u32, // number of required plows,
    child_plows: u32 // required plows of all children combined
}

Test 1

Group: 1, 2

Verdict: ACCEPTED

Test 2

Group: 1, 2

Verdict: WRONG ANSWER

Test 3

Group: 1, 2

Verdict: WRONG ANSWER

Test 4

Group: 2

Verdict: WRONG ANSWER

Test 5

Group: 2

Verdict: WRONG ANSWER

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: WRONG ANSWER

Test 11

Group: 2

Verdict: WRONG ANSWER

Test 12

Group: 1, 2

Verdict: WRONG ANSWER

Test 13

Group: 2

Verdict: WRONG ANSWER