树形DP初步-二叉树

时间限制: 1000 ms 内存限制: 65536 kb
总通过人数: 172 总提交人数: 174

题目描述

一道简单的'伪'树形dp。
注意题目难度与顺序无关,请自行决策,不要卡在一道题目上太久。

关于二叉树:

二叉树的递归定义:二叉树要么为空,要么由根结点,左子树,右子树组成。左子树和右子树分别是一棵二叉树。

请注意,有根树和二叉树的三个主要差别:

  1. 树的结点个数至少为1,而二叉树的结点个数可以为0;

  2. 树中结点的最大度数没有限制,而二叉树结点的最大度数为2;

  3. 树的结点无左、右之分,而二叉树的结点有左、右之分。

关于最长链:

最长链为这棵二叉树中一条最长的简单路径,即不经过重复结点的一条路径。可以容易证明,二叉树中最长链的起始、结束结点均为叶子结点。

现给出一棵N(N<=100000)个结点二叉树,问这棵二叉树中最长链的长度为多少,保证了1号结点为二叉树的根。

输入

输入第1行为包含了一个正整数N,为这棵二叉树的结点数,结点标号由1至N。

接下来N行,这N行中的第i行包含两个正整数l[i], r[i],表示了结点i的左儿子与右儿子编号。如果l[i]为0,表示结点i没有左儿子,同样地,如果r[i]为0则表示没有右儿子。

输出

输出包括1个正整数,为这棵二叉树的最长链长度。请注意,链长定义为经过的边的个数。

输入样例

6
2 3
4 5
0 6
0 0
0 0
0 0

输出样例

4

相关推荐