use proconio::input;

#[derive(Debug, Clone, Copy)]
enum Count {
    Finite(u64),
    Infinite,
}

#[derive(Debug, Clone)]
struct Item {
    weight: u64,
    value: u64,
    count: Count,
}

#[derive(Debug, Clone)]
struct FiniteItem {
    weight: u64,
    value: u64,
    count: u64,
}

fn knapsack_by_greedy_weight_to_cap(cap: u64, items: &[Item]) -> u64 {
    let mut value_sum = 0;
    let mut weight_sum = 0;
    for &Item {
        weight,
        value,
        count,
    } in items
    {
        let want = (cap - weight_sum) / weight;
        match count {
            Count::Infinite => return value_sum + want * value,
            Count::Finite(count) => {
                if want <= count {
                    return value_sum + want * value;
                }
                weight_sum += count * weight;
                value_sum += count * value;
            }
        }
    }
    panic!()
}

fn knapsack_by_dp_value_to_weight(items: &[FiniteItem]) -> Vec<u64> {
    let value_max = items
        .iter()
        .map(|item| item.value * item.count)
        .sum::<u64>() as usize;
    let mut dp = vec![std::u64::MAX; value_max + 1];
    dp[0] = 0;
    for &FiniteItem {
        mut weight,
        value,
        mut count,
    } in items
    {
        let mut value = value as usize;
        while 0 < count {
            for _ in 0..(if count % 2 == 1 { 1 } else { 2 }) {
                for i in (0..=value_max - value).rev() {
                    let j = i + value;
                    if dp[i] != std::u64::MAX {
                        dp[j] = dp[j].min(dp[i] + weight);
                    }
                }
                for i in (0..value_max).rev() {
                    dp[i] = dp[i].min(dp[i + 1]);
                }
                count -= 1;
            }
            weight *= 2;
            value *= 2;
            count /= 2;
        }
    }
    dp
}

fn main() {
    input!(
        n: usize,
        cap: u64,
        d: u64,
        m0: u64,
        mp: [(u64, proconio::marker::Usize1); n - 1]
    );

    let mut g = vec![vec![]; n];
    for (i, p) in mp.iter().enumerate().map(|(i, &(_, p))| (i + 1, p)) {
        g[p].push(i);
    }

    let mut weight: Vec<_> = std::iter::once(m0)
        .chain(mp.iter().map(|&(m, _)| m))
        .collect();
    let mut value = vec![1; n];
    let count: Vec<_> = std::iter::once(Count::Infinite)
        .chain(vec![Count::Finite(d); n - 1].into_iter())
        .collect();
    fn dfs(x: usize, p: usize, value: &mut [u64], weight: &mut [u64], g: &[Vec<usize>]) {
        for &y in &g[x] {
            if y == p {
                continue;
            }
            dfs(y, x, value, weight, g);
            value[x] += value[y];
            weight[x] += weight[y];
        }
    }
    dfs(0, 0, &mut value, &mut weight, &g);

    let items: Vec<Item> = weight
        .into_iter()
        .zip(value.into_iter())
        .zip(count.into_iter())
        .map(|((weight, value), count)| Item {
            weight,
            value,
            count,
        })
        .collect();
    let mut greedy = Vec::new();
    let mut dp = Vec::new();
    for &Item {
        weight,
        value,
        count,
    } in &items
    {
        match count {
            Count::Infinite => {
                greedy.push(Item {
                    weight,
                    value,
                    count,
                });
            }
            Count::Finite(count) => {
                dp.push(FiniteItem {
                    weight,
                    value,
                    count: count.min(50),
                });
                greedy.push(Item {
                    weight,
                    value,
                    count: Count::Finite(count - count.min(50)),
                });
            }
        }
    }
    greedy.sort_by(|l, r| (l.weight * r.value).cmp(&(r.weight * l.value)));

    println!(
        "{}",
        knapsack_by_dp_value_to_weight(&dp.into_iter().collect::<Vec<_>>())
            .into_iter()
            .enumerate()
            .map(|(dp_value, dp_weight)| {
                if dp_weight <= cap {
                    let greedy_value = knapsack_by_greedy_weight_to_cap(
                        cap - dp_weight,
                        &greedy.iter().cloned().collect::<Vec<_>>(),
                    );
                    Some(dp_value as u64 + greedy_value)
                } else {
                    None
                }
            })
            .filter_map(std::convert::identity)
            .max()
            .unwrap()
    );
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_knapsack_by_dp_value_to_weight() {
        fn brute(items: &[FiniteItem]) -> Vec<u64> {
            let value_max = items
                .iter()
                .map(|item| item.value * item.count)
                .sum::<u64>() as usize;
            let mut ans = vec![std::u64::MAX; value_max + 1];
            ans[0] = 0;
            let count_max: Vec<u64> = items.iter().map(|item| item.count).collect();
            let mut count = vec![0; count_max.len()];
            loop {
                let weight = items
                    .iter()
                    .zip(count.iter())
                    .map(|(item, count)| item.weight * count)
                    .sum::<u64>();
                let value = items
                    .iter()
                    .zip(count.iter())
                    .map(|(item, count)| item.value * count)
                    .sum::<u64>() as usize;
                ans[value] = ans[value].min(weight);
                if let Some(i) = count
                    .iter()
                    .zip(count_max.iter())
                    .enumerate()
                    .filter(|&(_, (x, y))| x < y)
                    .last()
                    .map(|p| p.0)
                {
                    count[i] += 1;
                    count[i + 1..].iter_mut().for_each(|x| *x = 0);
                } else {
                    break;
                }
            }
            for i in (0..ans.len() - 1).rev() {
                ans[i] = ans[i].min(ans[i + 1]);
            }
            ans
        }
        let items = vec![
            FiniteItem {
                weight: 3,
                value: 5,
                count: 4,
            },
            FiniteItem {
                weight: 4,
                value: 7,
                count: 3,
            },
            FiniteItem {
                weight: 5,
                value: 8,
                count: 2,
            },
        ];
        let brute = brute(&items);
        let dp = knapsack_by_dp_value_to_weight(&items);
        eprintln!("brute: {:?}", &brute);
        eprintln!("dp: {:?}", &dp);
        assert_eq!(brute, dp);
    }
}


Measured memory_bytes: 2552