树上三染色(Tree 3-Coloring)

题目描述

给定一棵 $n$ 个点的树，$1$ 号点是树的根，其中一些点已经有了颜色，颜色共三种，以 0，1，2 表示。请为还没有染色的点染色，要求每条边的两个端点颜色不能一样。请计算有多少种可行的方案。由于答案可能很大，输出方案数模 $10^9+7$ 的余数。

输入格式

第一行：两个整数 $n$ 和 $k$；

第二行：$n-1$ 个整数 $p_2,\dots,p_n$ 表示树上 $2$ 号点到 $n$ 号点各自的父亲编号；

接下来 $k$ 行：每行两个整数 $u$ 和 $c$，表示树上 $u$ 号点的颜色为 $c$（$0\leq c\leq 2$）。

输出格式

单个整数：表示染色的方案数模 $10^9+7$ 的余数。

样例输入 #1

4 1
1 1 1
2 0

样例输出 #1

8

样例说明 #1

只有一个叶子的颜色是确定，根可以有两种颜色，另外两个叶子可以各有两种颜色。

数据范围

• 对于 30% 的数据，$1\leq k\leq n\leq 20$；
• 对于 60% 的数据，$1\leq k\leq n\leq 5000$；
• 对于 100% 的数据，$1\leq k\leq n\leq 100000$。

知识点与难度

本题涉及的知识点从属于 GESP 6级（树形动态规划），难度等级：⭐⭐。

测试点分布