#1956. 火花
火花
火花
题目描述
标题: 火花 - Problem - QOJ.ac
#14579. 火花
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 分):无特殊限制。
输入格式
(见题面原文)
输出格式
(见题面原文)
数据范围
(见题面原文)
样例
样例 1
4 4 1
2 1
2 1
2 5
2 1
1 1 2
15