#PQJ2560x14579. QOJ 2560_14579

    ID: 2835 传统题 1500ms 2048MiB 尝试: 0 已通过: 0 难度: NOI/NOI+/CTS 上传者: 标签>来源:qoj.ac章节练习数据:双算对拍权威答案来源:集训队赛事:IOI 2026 互测贪心

QOJ 2560_14579

标题: 火花 - Problem - QOJ.ac

#14579. 火花

Statistics

The problem was used in the following contests:

This problem is prepared by raincity, Reliauk🕊, and zzzYheng .

愛し方さえも 君の匂いがした 即便是爱你的时候 也散发你的味道 歩き方さえも その笑い声がした 甚至连走路的时候 也充斥你那样的笑声

题目描述

  • 有一棵 n 个点、根为 1 的树。第 i 个点上有 ci 个物品,权值均为 vi。

  • 需要先选择 t 个不同的点,对于选的每个点,在它的每个祖先(包括自己)上各取一个物品。

    • 本题保证 t<ci,因此不会存在没有物品可取的情况。
  • 接下来可以取至多 k 个物品,要求所有在这一步被取了物品的点形成一个含根的连通块。

  • 最大化整个过程中取的物品权值之和。

输入格式

  • 第一行三个整数 n,k,t。
  • 接下来 n 行,每行两个正整数分别表示 ci 和 vi。
  • 最后一行 n−1 个正整数,第 i 个正整数表示点 (i+1) 在树上的父亲 fai+1。

输出格式

  • 一行,输出一个非负整数,表示最大的权值和。

样例

样例 1 输入
4 4 1
2 1 
2 1
2 5
2 1
1 1 2
样例 1 输出
15

数据范围

对于所有数据:1≤n,k≤104,0≤t≤n,t<ci≤109,1≤vi≤109,fai<i,nk(t+1)≤107。

  • 子任务 1(10 分):n,k,t≤10。
  • 子任务 2(20 分):t=0。
  • 子任务 3(15 分):nk(t+1)≤106。
  • 子任务 4(25 分):nk(t+1)≤5×106。
  • 子任务 5(30 分):无特殊限制。