1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
use std::cmp::max;
use std::collections::LinkedList;
use std::io::{self};

#[derive(Debug)]
#[allow(dead_code)]
struct Conference {
    idx: usize,
    required_ppl: u64,
    children: LinkedList<*mut Conference>,
}

#[derive(Debug)]
struct ConferenceDay {
    conferences: Vec<Conference>,
}

impl Conference {
    fn get_required_ppl(&mut self) -> u64 {
        let mut required_ppl = 1;

        if self.children.len() > 0 {
            required_ppl = self
                .children
                .iter()
                .map(|child| unsafe { &(**child).required_ppl })
                .sum();
        }

        self.required_ppl = required_ppl;
        required_ppl
    }
}

impl ConferenceDay {
    fn from_stdin(previous_day: &mut ConferenceDay) -> Self {
        let stdin = io::stdin();
        let mut line = String::new();

        stdin.read_line(&mut line).unwrap();

        let mut iter = line.split_whitespace();

        let n: usize = iter.next().unwrap().parse().unwrap();
        let mut conferences = Vec::with_capacity(n);

        for idx in 1..=n {
            let parent_idx: usize = iter.next().unwrap().parse().unwrap();
            let children: LinkedList<*mut Conference> = LinkedList::new();
            conferences.push(Conference {
                idx,
                required_ppl: 0,
                children,
            });
            let conference_ptr = &raw mut conferences[idx - 1];

            if parent_idx > 0 {
                let parent = &mut previous_day.conferences[parent_idx - 1];

                parent.children.push_back(conference_ptr);
            }
        }

        Self { conferences }
    }

    fn get_required_ppl(&mut self) -> u64 {
        let mut result = 0;

        for conference in self.conferences.iter_mut() {
            result += conference.get_required_ppl();
        }

        result
    }
}

fn main() {
    let stdin = io::stdin();
    let mut line = String::new();

    stdin.read_line(&mut line).unwrap();

    let mut iter = line.split_whitespace();

    let n: usize = iter.next().unwrap().parse().unwrap();
    let k: usize = iter.next().unwrap().parse().unwrap();

    let mut conference_days: Vec<ConferenceDay> = Vec::with_capacity(n);

    conference_days.push(ConferenceDay {
        conferences: (1..=k)
            .map(|idx| Conference {
                idx,
                required_ppl: 0,
                children: LinkedList::new(),
            })
            .collect(),
    });

    for i in 1..n {
        let previous_day = &mut conference_days[i - 1];
        let new_day = ConferenceDay::from_stdin(previous_day);

        conference_days.push(new_day);
    }

    let mut result = 0;

    for conference_day in conference_days.iter_mut().rev() {
        result = max(result, conference_day.get_required_ppl());
    }

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