TouchStone
  请登录后使用
登录 注册
 系统首页  练习题库  考试列表  判题结果  问题讨论与解答  统计信息与排名
  • 首页
  • 题库
  • P4570
  • 题目
  • P4570Arietta
    限制 : 时间限制 : 20000 MS   空间限制 : 565536 KB
    评测说明 : 2s,64m
    问题描述

    Arietta 的命运与她的妹妹不同,在她的妹妹已经走进学院的时候,她仍然留在山村中。
    但是她从未停止过和恋人 Velding 的书信往来。一天,她准备去探访他。
    对着窗外的阳光,临行前她再次弹起了琴。
    她的琴的发声十分特殊。
    让我们给一个形式化的定义吧。
    所有的 n 个音符形成一棵由音符 C ( 1 号节点) 构成的有根树,每一个音符有一个音高 Hi 。
    Arietta 有 m 个力度,第 i 个力度能弹出 Di 节点的子树中,音高在 [Li,Ri] 中的任意一个音符。
    为了乐曲的和谐,Arietta 最多会弹奏第 i 个力度 Ti 次。
    Arietta 想知道她最多能弹出多少个音符。

    输入格式

    输入共 m + 3 行。
    第一行两个整数 n, m ,意义如题目所述。
    第二行 n - 1 个整数 Pi ,表示节点 i ( i = 2 . . . n ) 的父亲节点的编号。
    第三行 n 个整数 Hi 。
    接下来的 m 行,每行四个整数 Li,Ri,D,Ti

    输出格式

    输出一个整数表示 Arietta 最多能弹奏多少音符。
    数据范围与约定
    对于 100% 的数据,1 ≤ n, m ≤ 10000 。
    对于所有数据,1 ≤ Hi , Ti , Pi ≤ n, 1 ≤ Li ≤ Ri ≤ n 。

    样例输入 1

    5 2
    1 1 2 2
    5 3 2 4 1
    1 3 2 1
    3 5 1 4

    样例输出 1

    4

    样例输入 2

    8 8
    1 7 3 2 1 1 1
    4 3 6 7 7 8 8 6
    5 5 3 1
    3 8 3 1
    3 4 1 1
    3 8 1 2
    1 2 3 1
    1 4 2 1
    1 7 8 1
    2 3 1 2

    样例输出 2

    6

    提示

    第一个力度弹奏音符5,第二个力度弹奏音符1,2,4。

    数据范围与约定
    对于 100% 的数据,1 ≤ n, m ≤ 10000 。
    对于所有数据1<=Hi,Ti,Pi<=N,1<=Li<=Ri<=N