给定一颗二叉树和一个整数 sum,求累加和为 sum 的最长路径长度。路径是指从某个节点往下,每次最多选择一个孩子节点或者不选所形成的节点链。
输入描述:
第一行输入两个整数 n 和 root,n 表示二叉树的总节点个数,root 表示二叉树的根节点。以下 n 行每行四个整数 fa,lch,rch,val,表示 fa 的左儿子为 lch,右儿子为 rch。val 表示 fa 节点的值(如果 lch 为 0 则表示 fa 没有左儿子,rch同理)


输出描述:
输出一个整数表示最长链的长度。
示例1

输入

9 1
1 2 3 -3
2 4 5 3
4 0 0 1
5 8 9 0
8 0 0 1
9 0 0 6
3 6 7 -9
6 0 0 2
7 0 0 1
6

输出

4
示例2

输入

9 1
1 2 3 -3
2 4 5 3
4 0 0 1
5 8 9 0
8 0 0 1
9 0 0 6
3 6 7 -9
6 0 0 2
7 0 0 1
-9

输出

1
加载中...