10415: 监控二叉树
[Creator : ]
Description
给定一个二叉树，我们在树的节点上安装摄像头。
节点上的每个摄影头都可以监视其父对象、自身及其直接子对象。
计算监控树的所有节点所需的最小摄像头数量。
节点上的每个摄影头都可以监视其父对象、自身及其直接子对象。
计算监控树的所有节点所需的最小摄像头数量。
Input
第一行一个整数 $n\ (1 \leq n \leq 5\times 10^5)$。
其后 $n$ 行，第 $i$ 行包括两个个整数 $lson, rson\ (1 \leq lson,rson \leq n)$。其中 lson,rson 分别表示编号为 $i$ 的节点的左儿子和右儿子编号，如果儿子不存在，则为 $-1$。
保证输入数据合法，一定可以构成一棵树。
其后 $n$ 行，第 $i$ 行包括两个个整数 $lson, rson\ (1 \leq lson,rson \leq n)$。其中 lson,rson 分别表示编号为 $i$ 的节点的左儿子和右儿子编号，如果儿子不存在，则为 $-1$。
保证输入数据合法，一定可以构成一棵树。
Output
一行一个整数，表示答案。
Sample 1 Input
4
2 -1
3 4
-1 -1
-1 -1
Sample 1 Output
1
如图所示，一台摄像头足以监控所有节点。
Sample 2 Input
5
2 -1
3 -1
4 -1
-1 5
-1 -1
Sample 2 Output
2
需要至少两个摄像头来监视树的所有节点。 上图显示了摄像头放置的有效位置之一。
Sample 3 Input
1
-1 -1
Sample 3 Output
1
2
2 -1
-1 -1
1
Sample 4 Input
2
-1 2
-1 -1
Sample 4 Output
1