黄黑树

[编程题]黄黑树

热度指数：238 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

小团作为一名美团骑手，最喜欢的颜色就是黄和黑，因此对包含这两种颜色的事物都格外留意。

这天他发现有一棵树，树上的每个节点都是黄的或者黑的。现在小团想知道对于这棵树中的每个节点，在以其为根的子树中，所有与其颜色不同的节点的深度之和是多少。子树中节点的深度被定义为该节点与该子树根节点之间的最短路径的边数。

输入描述:

第一行有一个数n，代表这棵树上一共有n个节点，编号为1~n。(1<n<=100000)

第二行有n个数，第i个数表示编号为i的节点的颜色，为0表示黄色，为1表示黑色。

第三行有n-1个数，第i个数表示编号为i+1的节点的父节点编号。

输出描述:

在一行中输出n个数，第i个数代表第i个节点的答案。

示例1

输入

10
0 0 1 0 0 1 1 1 0 0
1 2 3 4 4 5 7 6 9

输出

17 13 10 6 3 3 0 0 0 0

算法知识视频讲解

ChandlerR

发表于 2021-08-05 17:49:38

典型的递归。根据数据量10^5,如果每个节点都遍历生成结果显然超时，一次遍历实现的话要保证深度相对关系不变。设深度函数f(n,root),节点n对于根节点1的深度为f(n,1)，一个子树包含n,n相对于子树根节点root的深度为f(n,root),root相对于节点1深度为f(root,1),显然有展开全文