开始: 2023-10-20 11:00:00

1020模拟赛周赛05

结束: 2023-10-20 20:00:00
当前  2025-01-24 17:48:19  类型: IOI  状态: 已经结束 

P3. 树和数
描述

阿尔德希尔是须弥生论派的学者,他对生物学有很深的研究,同时他也对数学有着浓厚的兴趣。一天他正在化城郭散步,突然想到了下面这个问题:

二叉树是一种树型结构,它的特点是每个节点最多有两棵子树,且左右子树有左右之分,其左右顺序不能颠倒,如下图就是一颗二叉树。

一颗严格二叉树是指除叶子节点外任何一个节点均有两个子树的二叉树,如下图就是一颗严格二叉树。

一个表达式可以惟一对应一颗严格二叉树,这个二叉树的叶子节点为数字,其余节点为运算符,如 (1+2)*4-5/7 可以对应到下图的一颗严格二叉树中。

同理这样一颗严格二叉树同样可以对应到一个表达式,现在规定一个表达式的计算顺序为先进行运算等级高的运算,再计算运算等级低的,相同运算级按照从左往右的顺序计算,括号拥有最高的运算等级。

现在将上述的这样一颗二叉树的叶子节点全部去掉,只剩下 n 个表示符号的节点,如下图所示。

虽然去掉了叶子节点上的数字,表达式没有具体的结果,但它依然可以表示出运算的顺序,该二叉树对应了 (a + b) * c - d / e 这样一种运算顺序。现在给你一颗这样的只包含运算符号的二叉树,共有 m 中不同运算等级的运算符号,运算等级越高计算优先级越高,请你求出它对应的一个表达式中至少需要多少对括号才能使得运算顺序不变。

如上述二叉树同样也对应了 ((a+b)*c)-d/e((a+b)*c-d/e) 等运算顺序,但 (a+b)*c-d/e 需要的括号最少,只需要一对括号,若去掉这对括号运算顺序就会发生改变,所以答案为1


输入

第一行两个正整数n,\ m,表示二叉树有 n 个节点,共有 m 中运算等级不同的运算符号。

接下来 n 行每行包含三个正整数 l_i,\ r_i,\ x_i,表示第 i 个节点的左儿子节点编号(为 0 表示没有左儿子),右儿子节点编号(为 0 表示没有右儿子),当前节点运算符号的运算等级。保证 1 号节点是二叉树的根。


输出

输出一个正整数表示至少需要多少对括号才能使得运算顺序不变。

样例

输入

4 2
2 3 1
4 0 2
0 0 2
0 0 1

输出

1

输入

4 1
2 3 1
0 0 1
0 4 1
0 0 1

输出

2
提示

【数据范围】

n 表示输入序列的长度

+ 对于 30\% 的数据,n\leq 5

+ 对于 60\% 的数据,n\leq 500

+ 对于 100\% 的数据,n\leq 100000

样例1解释:

加法和减法的运算优先级为1,乘法和除法的运算优先级为2,该样例即为题面中所举的例子。

样例2解释:

该二叉树对应了 a + b+ (c + (d + e)) 的运算顺序,所以答案为2


提交

题目参数
时间限制 1 秒
内存限制 128 MB
提交