U231214 [全国青少年信息学联赛 CCF NOIP 2018] 小明的树(tree)
题目背景
[全国青少年信息学联赛 CCF NOIP 2018]小明的树 T2
------------
1.0s 512MB
题目描述
小明有一个二叉树,他每次可以选择一个点,将这个点到根节点的所有点的权值加上任意一个实数。
初始所有点的权值为 0
他想要将一些点的权值改变不为 0 ,想要一些点的权值继续保持0。
问最终他最多可以让多少点满足他的要求?
并且他希望在满足最多要求的同时选择点操作的次数最少
输入格式
第一行一个数表示二叉树的点数
第二行n-1 个数,第 i 个数表示第 i+1 个节点的父亲,其中第 1 个点没有父亲。
第三行一个 01 字符串,第 i 个位置为 1 表示希望 i 号点的权值不为 0,
输出格式
第一行一个数表示最多能让多少点满足他的要求
第二行一个数表示此时最少的操作次数是多少
说明/提示
【数据范围】
对于 30%的数据,n≤5
对于 60 的数据, n≤2000
对于另外 20%的数据,保证小明最多只希望一个点权值发生改变。
对于 100 的数据, n≤100000