#P16233. [2026保加利亚国家扩展队训练赛]Cherry Plum樱桃李

[2026保加利亚国家扩展队训练赛]Cherry Plum樱桃李

题目描述

萨什卡有一棵由 NN 个顶点构成的樱桃李树。顶点 11 位于树的最上方,并被定义为根。

除根以外,每个顶点最多生长一簇樱桃李。对于第 jj 簇果实,给定:

  • 它所在的顶点 VjV_j;
  • 它恰好成熟的日期 DjD_j;
  • 若在该日采下,可得到的果实数量 WjW_j。

萨什卡只能通过砍断树枝来采摘。

在任意一天,她可以同时砍断任意多条边。树会因此分裂成若干连通块,所有不再与根相连的部分都会掉落到地面。

对于每个掉落部分,她只会收获在当天恰好成熟的果实:

  • 尚未成熟就掉落的果实会浪费;
  • 一直留在树上直到过熟的果实也会浪费。

形式化地说,每天萨什卡可以删除任意多条树边。对于第 jj 簇果实,当且仅当在第 DjD_j 天,顶点 VjV_j 已经不再与根位于同一连通块中,她才能获得 WjW_j 的收益。

请计算萨什卡最多能够收获多少颗恰好成熟的樱桃李。

实现要求

你需要提交 cherryplum.cpp,包含 cherryplum.h,并实现:

long long solve(
    int N,
    int M,
    int K,
    const std::vector<int>& P,
    const std::vector<int>& V,
    const std::vector<int>& D,
    const std::vector<long long>& W
);

参数含义:

  • NN:树的顶点数;
  • MM:果实簇数量;
  • KK:最晚成熟日期;
  • P 长度为 N−1N-1,其中 P[i] 是顶点 i+2i+2 的父亲;
  • V[j]、D[j]、W[j] 描述第 jj 簇果实所在顶点、成熟日期和收益。

保证 V 中的顶点两两不同。

函数只会被调用一次,应返回最大总收益。

数据范围

  • 2≤N≤100 0002\le N\le 100\,000;
  • 1≤M≤N−11\le M\le N-1;
  • 1≤K≤100 0001\le K\le 100\,000;
  • 2≤Vj≤N2\le V_j\le N;
  • 1≤Dj≤K1\le D_j\le K;
  • 1≤Wj≤1091\le W_j\le 10^9。

子任务

子任务 分值 依赖子任务 额外限制
0 - 样例
1 5 N,K≤20N,K\le 20,且所有 Wj=1W_j=1
2 3 果实只生长在叶子上
3 9 Pi=i−1P_i=i-1,且所有 Wj=1W_j=1
4 10 K≤2K\le 2
5 13 1 K≤20K\le 20,且所有 Wj=1W_j=1
6 11 0,1 M≤1000M\le 1000
7 19 1,3,5 所有 Wj=1W_j=1
8 30 0-7 无额外限制

本地评测器格式

输入

N M K
P2
P3
...
PN
V1 D1 W1
V2 D2 W2
...
VM DM WM

输出

输出 solve 的返回值。

样例

输入:
6 4 10
1
2
1
4
4
3 4 5
4 7 2
5 4 1
6 9 3

输出:
9

一种最优方案为:

  • 第 44 天,砍断顶点 44 与 55 之间的边,收获顶点 55 的 11 颗果实;同时砍断顶点 11 与 22 之间的边,收获顶点 33 的 55 颗果实;
  • 第 77 天不操作,放弃顶点 44 的果实;
  • 第 99 天,砍断顶点 11 与 44 之间的边,收获顶点 66 的 33 颗果实。

总收益为 1+5+3=91+5+3=9。

@下发文件