树的题

​【​​​题目描述​】

⼆叉树是⼀种树型结构，它的特点是每个节点最多有两棵⼦树，且左右⼦树有左右之分，其左右顺序不能颠倒。而⼀颗严格⼆叉树是指除叶⼦节点外任何⼀个节点均有两个⼦树的⼆叉树。⼀个表达式可以唯一对应⼀颗严格⼆叉树，这个⼆叉树的叶⼦节点为数字，其余节点为运算符，如（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⾏每⾏包含三个正整数li,ri,xi，表⽰第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

【数据说明】

对于20%的点：n,m<=2;

对于40%的测试点：n,m<=20;

对于60%的测试点：n,m<=5000;

对于另20%的测试点：保证m=1;

对于100%的测试点：n,m<=10​^5;