考虑以 1 号点为根构造一棵树。
对于每条边 u-v
,其中 v 是 u 的儿子。
则砍掉 u-v
这条边,将树分为了 以 v 为根的子树
和 以 0 为根的树上砍掉以 v 为根的子树
这两部分。
小美是一位著名的冒险家,他经常在各种森林里探险。今天,他来到了道成林,这是一片美丽而神秘的森林。在探险途中,他遇到了一棵 n 个节点的树,树上每个节点都被涂上了红、绿、蓝三种颜色之一。
小美发现,如果这棵树同时存在一个红色节点、一个绿色节点和一个蓝色节点,那么我们就称这棵树是多彩的。很幸运,他发现这棵树最初就是多彩的。
但是,在探险的过程中,小美发现这棵树上有一条边非常重要,如果砍掉这条边,就可以把这棵树分成两个部分。他想知道,有多少种砍法可以砍掉这条边,使得砍完之后形成的两棵树都是多彩的。
第一行个整数 n ,表示节点个数
第二行 n−1 个整数 p2,p3,…,pn , pi 表示树上 i 和 p 两点之间有一条边。保证给出的定是一棵树。
第三行一个长度为 n 的字符串,第 i 个字符表示第 i 个节点的初始颜色。其中 R 表示红色, G 表示绿色, B 表示蓝色。
保证字符串只由这三种大写字母构成对于全部数据, 3≤n≤105 。
输出一行,一个正整数,表示答案。
输入
7
1 2 3 1 5 5
GBGRRBB
输出
1