TouchStone
  Please Login
ログイン 登録
距离明年CSP第一轮: ??天 距离CSP第二轮: ??天 距离NOIP还有: ??天
 ホームページ  問題セット  試験一覧  提出状況  掲示板  統計情報
  • ホーム
  • 問題セット
  • P5939
  • 問題
  • P5939「CEOI2019」魔法树
    制限 : 時間制限 : 20000 MS   メモリ制限 : 1048576 KB
    審判説明 : 2S,1024MB
    問題説明

    译自 CEOI 2019 Day2 T2「Magic Tree

    现在有一颗魔法树,总共有 \(n\) 个节点,编号从 $1$ 至 \(n\)。$1$ 节点是它的根。除 $1$ 节点外的每个节点最多长有一个魔法果实。一个长在 \(v_j\) 节点的魔法果实恰会在第 \(d_j\) 天成熟,在成熟时将其收获可以获得 \(w_j\) 单位的果汁。

    每天你可以砍下树上的某些边,然后当天与 $1$ 节点不再联通的果实如果恰好在当天成熟,则能够收获该果实的果汁。

    请找出最优方案下,总共能够收获的果汁量。

    点此提交

    入力形式

    第一行三个正整数 \(n, m, k\),分别表示节点数,果实数,所有果实成熟时间的上限。

    接下来共 \(n-1\) 行,每行一个正整数分别为 \(p_2, p_3, \dots, p_n\)\(p_i\) 表示 \(i\) 节点的父亲。

    接下来共 \(m\) 行,每行三个正整数 \(v_j, d_j, w_j\),分别表示该果实生长的节点编号,成熟日期,能收获的果汁。保证 \(v_j\) 互不相同。

    出力形式

    输出一行一个整数,表示最优方案下,总共能够收获的果汁量。

    サンプル入力

    6 4 10
    1
    2
    1
    4
    4
    3 4 5
    4 7 2
    5 4 1
    6 9 3

    サンプル出力

    9

    ヒント

    对于 \(100\%\) 的数据,保证 \(2\le n \le 10^5, 1\le m \le n - 1, 1\le k \le 10^5, 1\le p_i \le i - 1, 2\le v_j \le n, 1\le d_j\le k, 1\le w_j \le 10^9\)

    Subtask # 分值 特殊限制
    $1$ $6$ \(n, k\le 20, w_j = 1\)
    $2$ $3$ 果实都生长在叶子上
    $3$ $11$ \(p_i = i-1, w_j = 1\)
    $4$ $12$ \(k\le 2\)
    $5$ $16$ \(k\le 20, w_j = 1\)
    $6$ $13$ \(m\le 10^3\)
    $7$ $22$ \(w_j = 1\)
    $8$ $17$

    样例解释

    • 在第 $4$ 天,砍下 $5$ 号节点连接父亲的边,从 $5$ 号节点上的果实收获 $1$ 单位的果汁。砍下 $2$ 节点连接父亲的边,从 $3$ 号节点上的果实收获 $5$ 单位的果汁。
    • 在第 $9$ 天,砍下 $4$ 号节点连接父亲的边,从 $6$ 号节点上的果实收获 $3$ 单位的果汁。